CT45040

Minstrel and the Build Order

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Minstrel runs the bakery at the northern keep of Frostgate. 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 <= 3313; 0 <= m <= 3313.

Example 1:

Input: 1062 906 876 903 214 846 181 885 106 957 3 661 161 889 231 752 663 970 1 777 292 505 497 762 400 805 721 855 54 851 746 830 266 309 109 289 631 724 260 523 379 814 258 566 309 554 498 833 878 954 736 1048 183 340 395 637 774 1050 466 503 278 625 561 1038 620 1055 1 943 135 1058 869 1043 112 899 492 773 623 699 229 324 581 662 571 1037 657 773 782 1050 1026 1046 200 703 533 1045 704 853 101 173 588 772 39 506 215 845 68 768 304 524 58 916 31 555 133 993 149 678 754 790 559 739 745 904 287 453 466 838 397 885 429 560 9 226 830 915 31 837 306 981 536 994 110 678 969 1053 314 485 37 904 272 853 33 770 537 559 38 1053 655 704 194 888 329 385 406 806 372 679 29 93 132 344 459 707 372 795 382 591 63 1053 67 210 825 848 127 424 122 856 827 1003 604 1051 820 864 265 363 459 821 617 1042 30 55 129 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: 912 1059 778 779 543 558 729 820 171 515 357 843 652 657 262 705 288 693 243 791 277 430 7 717 446 504 591 690 132 728 451 807 572 835 489 618 38 243 63 68 99 900 468 517 684 887 415 801 449 534 768 895 233 845 87 597 169 862 569 814 54 313 431 822 578 787 64 541 408 733 79 206 773 817 694 801 161 242 35 590 170 730 508 723 681 834 217 630 142 892 289 423 147 170 123 253 661 778 147 857 281 715 197 445 25 866 96 838 733 824 645 729 444 448 673 912 125 328 46 572 117 226 433 656 132 711 208 487 61 661 511 599 47 529 280 493 37 393 684 825 652 840 379 614 110 432 187 799 27 682 85 398 41 501 301 599 555 887 358 569 489 736 238 883 349 600 254 832 556 705 218 525 302 606 505 617 244 518 301 509 193 854 32 883 419 610 555 658 82 717 570 600 170 744 710 839 359 386 452 716 13 367 115 486 431 44…
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: 1765 1699 292 669 739 762 226 1213 315 1642 152 1309 603 1217 530 1746 1325 1505 1326 1340 734 1047 986 1461 357 615 439 1622 966 996 1603 1641 1588 1690 184 1072 229 232 195 1419 387 1453 1676 1745 1374 1681 688 1665 745 1015 603 655 1606 1679 1481 1499 394 1095 392 824 686 890 1131 1434 562 1190 233 803 611 1617 1015 1372 720 1656 574 1732 1500 1542 514 651 1712 1727 298 1752 82 1234 118 1376 108 753 492 954 858 1638 922 971 1490 1613 53 852 322 565 1083 1317 537 1519 879 1630 176 1096 801 1628 1396 1730 953 1635 360 610 40 237 16 1374 1280 1282 551 1678 642 1431 641 1296 49 675 1175 1741 66 161 731 1701 495 968 451 1164 801 1040 740 1673 751 1645 134 150 542 796 504 1480 769 862 616 1033 242 1572 43 953 941 1694 487 757 801 1383 488 1028 40 325 169 587 531 1747 414 1529 120 880 228 1179…
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 <= 3313; 0 <= m <= 3313.

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