CT53139

The Bright Build Order

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

At the desert outpost of Sandspire, Dante records each bridges in a worn leather ledger. The guild wants answers, not guesses. 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 <= 3926; 0 <= m <= 3926.

Example 1:

Input: 2612 3548 2114 2117 1955 2060 195 1535 1686 2420 372 764 31 131 2535 2566 2008 2088 1935 2071 121 277 1302 2358 473 1770 1368 2600 140 1584 603 922 253 1776 1147 2002 898 1436 26 1552 1367 2111 2022 2179 1189 2583 2226 2560 1172 2061 318 1544 1023 1357 254 2291 323 2543 187 2059 1309 2048 1291 2142 1324 1341 158 1202 689 861 2473 2485 839 1811 1532 1993 224 1257 229 1460 1451 1511 1987 2353 1651 1866 162 771 81 1145 431 437 931 1987 965 1202 1283 2259 38 2051 509 1251 237 1259 1436 2480 1085 2018 1306 1922 1048 2372 2281 2441 153 1328 1625 1867 1477 2172 718 816 116 647 669 1089 6 72 2046 2476 930 998 262 2320 1814 1858 375 690 1869 2100 892 2419 21 1925 180 212 1098 1368 376 2264 315 2609 783 1373 1482 1716 792 1015 489 808 376 751 2114 2462 1213 1684 398 1844 357 1343 1669 2278 714 2528 …
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: 2456 3030 644 659 259 1756 1118 2253 1104 2371 1936 2090 1812 2129 660 1293 610 902 141 409 1156 1351 58 1839 718 1778 192 531 1268 2171 1365 1739 337 1384 1213 1352 493 1024 523 2104 1003 1821 672 1839 295 2394 564 2249 978 1281 193 196 474 1989 1897 2190 773 2432 1649 2197 875 1583 32 1053 550 1320 1707 1893 436 2254 831 1917 469 2072 1101 2360 16 1159 694 1043 824 1534 1417 2224 771 1609 1150 1584 592 1558 1062 1346 1021 2047 386 1969 992 1909 1482 1640 397 725 439 2038 1080 1249 443 1669 1455 1808 323 1529 1379 2027 271 893 734 2325 1053 2104 977 2369 468 2419 41 1293 974 2031 1923 2243 348 1594 500 803 146 1535 833 1353 450 698 86 2283 5 1761 663 2121 1793 1926 1301 1415 319 1117 454 2282 627 772 1245 1556 2003 2187 1948 2307 1310 1942 791 2028 337 1921 840 1601 1044 2217 909 930 821 …
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 3:

Input: 3802 1553 1386 1533 2910 3571 2172 2639 1600 1867 120 775 21 1049 317 453 349 3230 142 833 1490 1722 10 2496 2610 3575 706 1900 459 682 509 2688 807 2306 390 2953 1532 3320 1568 3168 287 1742 75 413 260 2339 2024 3765 290 1417 130 2153 65 1912 784 1346 1089 2485 566 1162 2798 2922 215 2811 168 960 433 1275 905 1018 213 2939 83 2506 1008 3435 2154 2829 962 2512 1123 1484 23 948 359 1281 3274 3618 2248 3752 494 495 1895 2816 1041 2820 2968 3539 2707 3549 1299 1541 1236 2353 221 2631 1998 2258 3312 3496 1119 2418 929 1848 1866 2210 1033 2059 941 1007 708 1356 1245 2681 1725 2313 544 2852 395 1802 372 3397 275 1704 2810 3336 2160 3485 1521 3041 137 407 479 2267 788 1729 2944 3514 1567 2469 2160 3365 1718 2801 1853 3480 502 1194 332 2955 913 2653 1822 1984 1134 3408 325 2043 2162 2345 50 3570 6…
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 <= 3926; 0 <= m <= 3926.

Loading...
Test Cases:No test cases
No test cases available.
The Bright Build Order - MEDIUM Coding Problem | CodeTikki