CT41747

Curator and the Build Order

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Morning light hits the fjord village of Deepwater as Curator unrolls the day's manifest of tunnels. The tally will decide the next shipment. Task: Edges u -> v mean u must come before v. Print the lexicographically smallest valid ordering of the n jobs (space-separated), or IMPOSSIBLE if a cycle exists. Input format: First line: n and m. Next m lines: u v. Output format: Print the order or IMPOSSIBLE. Constraints: 1 <= n <= 3451; 0 <= m <= 3451.

Example 1:

Input: 2831 2420 940 1658 338 1371 929 1437 326 2337 774 2023 488 899 948 1761 280 2622 1624 2685 439 749 1335 2664 509 1154 152 2826 2401 2493 1034 1562 2242 2603 1737 2210 890 1971 461 2680 834 1177 627 2536 637 1301 106 136 683 702 1181 2787 922 1551 1508 2604 1277 2347 111 2297 318 2228 2125 2482 1175 2464 1678 2369 841 1357 596 2063 641 1579 845 900 988 2566 51 2167 2249 2253 1670 2441 919 1752 555 2390 327 374 574 780 1583 1686 1643 1949 1531 2083 1221 2496 1205 2500 226 1382 932 2715 163 1903 283 1296 71 1083 655 2488 1530 1824 313 1895 519 2746 264 1659 2000 2117 171 1935 1398 2811 558 583 2191 2630 490 1406 1393 2134 1964 2097 123 1847 216 1312 509 2296 2670 2778 1065 1190 1971 2224 194 267 1617 1967 236 2648 1003 1449 899 1329 2248 2473 1803 2218 1215 1659 495 2000 1054 1955 187 2776 15…
Output: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 …

Example 2:

Input: 198 631 101 102 46 164 131 155 62 188 77 105 34 102 103 176 22 143 52 183 61 64 79 169 60 173 168 195 12 56 5 15 54 158 144 165 72 174 172 186 108 160 28 117 12 157 44 78 159 192 4 105 64 74 120 179 23 43 20 94 3 77 24 117 34 179 96 184 5 57 106 178 100 188 116 187 100 102 35 194 82 149 13 115 88 135 65 111 103 171 126 141 94 156 110 190 117 129 141 184 175 191 4 138 99 134 70 152 5 82 22 58 92 143 27 182 53 136 112 184 1 11 74 147 105 124 8 92 46 136 20 195 45 69 28 50 19 48 139 188 48 197 5 88 92 124 98 169 27 196 20 172 52 192 37 164 53 135 150 174 62 89 35 193 23 100 71 94 99 133 160 190 78 166 118 132 54 136 27 133 82 85 62 175 169 182 85 111 168 185 72 99 11 19 125 156 5 193 114 148 30 43 188 189 97 135 83 162 9 150 32 157 143 165 50 106 51 81 99 150 67 120 3 177 65 163 121 143 128 1…
Output: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198

Example 3:

Input: 1631 2085 1271 1536 1215 1530 1298 1608 883 1335 720 774 291 1100 1392 1577 70 384 292 1480 878 1552 526 1291 1400 1628 289 1115 39 1056 576 1443 265 664 419 578 436 572 577 1200 142 294 762 1045 114 366 1476 1483 1190 1306 234 946 54 951 1406 1460 314 1195 266 1369 209 1527 478 907 43 303 27 833 39 1307 1022 1424 77 1447 438 1421 164 1534 293 476 631 663 465 667 220 608 80 1311 401 842 614 1510 1433 1613 202 1613 1337 1558 497 1326 166 1532 1533 1600 737 1385 502 707 104 226 670 916 242 1566 612 1233 807 1548 698 779 1037 1508 1524 1569 528 701 965 1453 942 1010 768 821 1236 1558 1017 1127 6 929 889 1396 750 1286 350 908 460 1173 266 853 201 1082 905 1308 251 428 1351 1565 190 363 980 1395 269 1461 431 594 1128 1581 152 753 984 1285 252 331 598 685 571 853 1190 1387 336 1550 459 1303 166 …
Output: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 …

Constraints:

1 <= n <= 3451; 0 <= m <= 3451.

Loading...
Test Cases:No test cases
No test cases available.