CT54788

The Build Order of Lodebarrow

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Yash runs the boathouse at the silver mines of Lodebarrow. Today the books show a list of roads, and the numbers must be worked out before sundown. 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 <= 3242; 0 <= m <= 3242.

Example 1:

Input: 1108 2974 389 750 482 729 341 742 509 540 297 725 554 566 370 989 899 1026 476 1051 210 268 50 115 428 500 296 927 24 476 759 860 250 868 179 891 494 520 850 1096 360 1015 71 878 51 656 323 907 210 540 439 875 575 688 753 1010 48 472 31 252 234 567 53 553 102 285 168 612 499 701 475 801 472 515 855 872 214 413 166 639 254 982 231 542 996 1028 225 293 432 506 724 809 369 1065 406 887 721 939 668 905 163 220 253 671 141 1044 241 1031 355 786 383 583 932 1102 91 1102 104 234 37 359 241 923 101 368 389 628 227 293 734 972 961 1020 669 948 37 258 392 786 632 958 490 827 8 1098 510 672 544 919 694 1049 605 978 33 161 296 822 180 232 587 965 446 707 53 370 497 989 252 594 12 1064 45 529 459 492 73 1104 719 1024 101 399 168 951 481 898 640 801 399 451 442 724 843 1102 113 675 494 901 376 883 868 9…
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: 1895 3124 376 1585 1310 1518 905 1560 1235 1416 282 1312 282 1441 438 464 21 199 1595 1886 335 1110 766 975 989 1056 908 1641 351 1613 90 944 1303 1543 1661 1775 999 1874 736 773 183 796 546 1200 641 1698 61 884 1185 1866 1814 1857 294 791 1245 1806 899 1389 329 1434 1081 1294 1103 1786 686 1322 137 521 1310 1669 1353 1406 857 959 506 945 591 1097 261 833 959 1653 763 1513 525 1576 479 1835 191 1580 1131 1505 73 1032 178 1614 282 1782 77 1708 1555 1880 148 253 586 758 17 156 237 842 1283 1653 1129 1164 822 1385 385 453 623 1329 1116 1560 565 1496 380 1434 461 835 692 846 346 895 358 1198 245 422 271 579 66 74 526 713 803 926 360 1469 327 682 1709 1785 657 1168 56 1737 259 1356 1205 1422 485 858 217 1547 96 238 304 1833 302 1204 1480 1744 191 1209 248 767 1276 1449 755 1029 482 1375 1376 18…
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: 3114 1445 2009 2935 414 3039 236 1490 643 2441 755 1361 2030 2078 2741 2893 1255 1410 871 1026 425 1087 2749 2817 1923 2358 252 2800 318 1770 2322 3062 2183 2592 600 1816 1397 2999 75 1103 406 1099 369 931 2675 3043 1430 2393 1448 2932 515 2793 1949 2852 1595 2260 939 2662 650 2967 505 2873 2417 2758 1179 2922 1300 1665 2086 2129 1547 2822 2632 2820 1377 2939 1766 2377 2589 2731 207 856 1035 1319 767 2372 1084 1445 243 1393 560 2653 383 537 703 1048 207 1523 2135 2206 2830 2924 437 2776 692 3002 2404 2441 1122 2706 1709 2402 1392 2483 1602 2605 1586 2495 2119 2812 156 1095 1010 2756 2024 2760 1479 2017 2492 2594 1535 2595 1450 2208 408 3058 319 1413 1807 3083 655 809 69 2616 52 3068 1178 1306 2545 2740 224 2004 2316 2551 2316 2698 546 2622 802 1973 84 1176 445 2012 70 1975 1099 1552 1406 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 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 <= 3242; 0 <= m <= 3242.

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