CT43226

Zara and the Build Order

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

At the lily shoals of Padmore, Zara records each canals 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 <= 3930; 0 <= m <= 3930.

Example 1:

Input: 3038 2513 776 2980 135 353 850 918 104 2947 370 904 880 1310 45 2487 431 1064 2287 2417 732 2289 626 2642 2510 2744 823 2355 329 2235 218 619 220 1006 424 2475 364 2175 1237 2342 866 1461 195 1262 279 666 582 1574 260 2425 1292 1873 1280 2370 890 1088 764 2199 1300 1478 1587 2033 2844 2967 2420 2661 2803 2877 1698 1895 622 2854 1076 2214 1914 2017 145 1907 1570 1779 467 2550 437 2955 189 1624 450 2534 701 1431 2228 2243 1036 2382 1231 1589 2108 2852 1467 1527 2175 2726 2374 2973 1176 1487 450 2038 962 2020 823 1911 129 737 2737 3011 1887 1981 2706 2969 532 2288 1701 1993 1617 2854 299 2417 894 2020 485 2167 207 1775 10 2629 1731 1917 1414 2475 1092 2065 844 2447 792 1493 645 1264 852 1748 1659 2772 805 2955 2657 2772 1174 2708 729 1397 243 2905 1216 1648 992 1075 2833 2875 2069 2716 1158 2…
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: 3842 2590 3059 3071 3393 3813 534 1737 1267 3219 1995 3058 1477 2590 761 2753 2230 3140 1681 2932 455 3247 49 2529 2084 3529 1303 1547 1505 3631 3187 3771 586 2930 451 3579 2041 3400 357 1611 464 1134 678 1139 1867 3294 886 2366 455 3446 539 854 1341 3521 964 1222 3527 3598 644 1607 747 1073 135 3834 306 737 2184 2850 1230 2688 2041 2895 107 1776 1292 3328 438 1726 3 2608 1152 2155 2229 3765 1177 1544 433 3619 2936 3554 718 2481 1761 3562 3176 3470 1599 2343 1378 2540 1479 1570 1169 3208 1104 2408 2967 3482 1867 2260 237 2874 1786 2019 1657 2880 1203 2989 2411 3373 682 943 475 3583 2140 3164 1146 2564 2040 2110 1355 2676 600 750 2530 2591 628 2195 26 3728 2234 2333 2291 2698 1706 2841 727 3307 1863 3505 540 3282 287 3717 207 473 1545 3226 2094 2634 2060 2659 2886 3516 426 1251 1653 2027 40…
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: 2773 136 9 2231 1487 1594 900 2106 295 1106 59 729 495 1684 105 2540 758 2319 581 2109 69 470 409 530 824 2210 719 1940 474 2704 1207 1593 953 1814 837 1754 58 2129 697 1563 40 345 591 2401 280 1825 1560 2557 599 2275 1316 1892 2265 2694 3 2487 1557 1653 418 817 1345 2102 680 875 38 2229 284 2414 866 1855 542 805 460 2505 190 1366 11 639 2401 2608 190 754 306 473 412 457 148 2403 2356 2597 71 1333 2003 2169 1489 2771 1292 2160 949 1303 2091 2703 620 2557 1092 1292 2475 2591 1494 1880 835 1614 193 410 1142 1498 2242 2721 1644 1729 1824 2496 1147 2528 2326 2449 1671 2359 697 1550 1088 2116 350 1490 385 1101 790 963 1637 2376 902 2084 58 2268 65 132 2392 2583 1834 2340 2400 2739 2249 2397 1298 1561 287 465 1907 2149 933 1619 763 1436 411 1030 638 2335 1123 2023 1894 2568 72 1908 132 2584 1290…
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 <= 3930; 0 <= m <= 3930.

Loading...
Test Cases:No test cases
No test cases available.
Zara and the Build Order - MEDIUM Coding Problem | CodeTikki