CT61560

Boris and the Build Order

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Boris runs the tannery at the acacia flats of Thornveld. Today the books show a list of routes, 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 <= 2981; 0 <= m <= 2981.

Example 1:

Input: 849 2981 429 611 183 270 574 743 618 748 113 659 102 626 448 458 192 577 189 807 301 491 31 368 62 706 125 297 15 791 142 409 441 548 283 431 195 318 562 655 70 537 397 671 469 691 101 736 29 749 392 746 137 280 135 572 24 755 241 247 19 123 43 307 44 99 317 745 140 490 185 478 112 401 715 768 257 556 720 789 121 161 333 657 549 794 71 153 306 754 139 676 381 834 14 625 226 443 100 562 546 750 691 801 78 585 130 186 336 732 127 263 292 718 138 200 198 738 485 796 77 844 144 370 646 847 448 620 113 462 97 654 154 339 791 806 209 746 584 748 398 454 263 383 607 755 173 558 268 276 294 770 423 846 429 575 6 488 676 757 468 694 24 431 438 809 144 443 82 104 66 838 35 96 19 571 16 116 93 237 345 775 122 130 275 359 824 846 409 569 153 517 440 839 107 239 145 260 424 500 39 202 118 558 137 252 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 …

Example 2:

Input: 1381 2350 333 792 1278 1332 723 1364 1056 1207 777 906 21 471 750 1282 1026 1295 964 1093 995 1359 647 1118 933 1295 31 510 113 287 132 959 111 1367 413 582 98 1379 595 603 726 1094 698 920 723 1090 561 866 395 1053 915 1149 166 1034 159 1217 359 457 191 196 633 740 802 1065 419 584 957 1205 551 747 293 773 33 1193 375 465 63 404 34 819 942 1093 306 1184 581 616 390 1053 1164 1287 886 947 338 500 191 1055 370 569 852 901 1119 1235 496 1379 95 883 735 1312 69 1192 190 1261 62 577 1175 1373 359 978 421 430 404 1312 503 1264 23 1284 677 1251 1139 1319 577 815 810 1285 926 949 15 339 64 851 369 940 158 587 865 1341 885 1301 49 1067 474 1215 95 755 354 933 473 539 237 829 176 450 516 978 76 659 297 1301 510 788 475 1025 32 425 481 1330 1335 1359 24 1027 458 778 138 914 454 1106 505 629 788 1104…
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: 2842 569 1286 2512 1106 2382 1021 1967 553 1571 399 2157 1506 2670 2188 2291 1798 1977 364 2787 212 2606 9 1911 641 1431 191 1584 527 2416 551 1284 1399 1901 300 2502 845 2276 813 986 699 1397 1657 2525 1225 2714 57 2542 1619 2048 1966 2072 1132 1682 2716 2804 1661 2841 1435 2565 775 1687 742 1239 377 2459 294 398 434 1707 193 630 462 2545 184 328 1284 2017 935 1833 1626 1823 1021 1839 1698 1722 74 2481 1642 1826 896 1519 653 1713 638 1784 1076 2196 515 1578 1764 1812 360 2248 954 993 563 1592 285 2022 848 1225 129 251 451 1673 444 1919 9 957 592 1426 1237 1561 249 1302 246 2409 1298 2102 624 2039 425 2341 1824 1938 782 2787 637 1116 1348 2238 2393 2638 1112 2431 1217 1249 76 386 237 1378 734 2740 1040 1952 116 1849 339 1279 138 1460 1446 1898 272 822 147 2752 926 2827 1240 1830 691 2222 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 <= 2981; 0 <= m <= 2981.

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