CT42694

The Ember corridors of Qadir

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Every season at the archive halls of Scrollkeep, someone must prepare the guildmaster's brief. This year the task falls to Qadir, armed only with the corridors register. 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 <= 3764; 0 <= m <= 3764.

Example 1:

Input: 911 3590 68 486 567 587 419 475 656 686 152 710 103 545 59 809 331 823 118 247 176 415 260 423 569 735 418 599 336 595 233 702 408 459 380 872 469 847 129 160 249 661 227 751 538 776 296 880 138 139 13 863 571 664 198 543 332 465 720 768 64 218 275 845 604 673 177 742 7 473 165 302 281 810 393 815 456 581 429 587 10 515 36 172 305 711 43 288 712 819 250 266 171 465 80 293 25 796 620 911 135 318 19 771 54 439 104 348 212 226 22 211 632 640 435 524 153 683 16 369 417 642 694 701 192 430 282 419 207 460 591 809 179 284 9 71 532 587 486 784 336 788 35 91 159 784 326 589 646 859 328 853 538 770 588 888 107 330 87 722 9 149 33 796 135 227 213 521 133 770 587 605 17 351 278 733 393 626 319 900 684 866 65 129 248 737 300 650 390 717 97 184 143 712 597 621 47 391 402 545 693 809 183 221 120 640 487…
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: 3151 2195 274 1011 273 1542 819 3085 1080 1603 502 2545 1055 1769 1725 2827 1243 1575 416 1770 1205 1960 56 2220 733 2476 423 2347 1616 2250 1827 1989 428 2488 134 1622 667 2391 1449 2609 2892 3093 498 1792 1826 1972 1120 2567 5 2094 1453 1572 49 1090 2287 2386 2614 2950 602 2637 2226 2509 1775 2378 360 2000 682 2728 1076 1111 750 1250 549 689 2285 2708 706 896 39 768 1372 2445 1349 1587 2385 2963 394 1915 2054 2317 1755 2100 18 2131 1867 3018 575 2002 1486 2815 1951 2494 754 1300 1730 2362 1076 2828 133 1170 2296 2731 636 2106 803 1598 95 144 122 2536 2260 2899 935 1128 907 1897 185 2108 921 2796 2893 3023 915 2985 1641 2394 210 2443 2025 2704 2792 3130 292 1913 961 1739 293 2442 825 1379 169 2291 2026 2604 1005 1234 960 1631 1650 2930 1833 1854 283 1946 3054 3132 214 2471 1566 2216 1144 …
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: 3638 3112 1901 2967 421 898 3191 3249 1989 2839 2561 2811 1363 2756 1137 2323 1195 1552 2156 2328 1407 3551 2068 2085 2118 2803 7 2909 1083 1616 613 1307 871 2408 619 3438 365 532 3020 3090 1995 2883 1153 1819 2688 3361 2308 3156 282 550 1122 1653 737 3464 1800 3583 2977 3158 498 817 726 1994 1143 3474 347 1282 1489 3457 907 1661 1646 2411 616 1656 558 2633 1683 2024 1443 3321 600 1699 397 2015 589 2903 637 3405 1688 1802 830 1396 1275 3129 2113 3193 1053 3338 2437 2528 942 1012 1576 2373 427 900 901 3281 414 2370 14 3568 400 3516 1322 3343 2669 3094 786 2061 951 2681 2580 2883 3231 3526 1649 2518 21 1374 647 3594 2155 3368 3033 3038 1214 3057 252 3293 1709 1742 839 1140 821 2876 3380 3565 1346 2383 683 2030 3290 3300 237 3067 2878 3197 185 2241 1765 1949 1712 2079 1168 3050 930 995 178 53…
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 <= 3764; 0 <= m <= 3764.

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