CT42569

The Build Order of the Tempest roads

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

The measurer Vesper has been asked to schedule the next expedition. On the desk lies a long table of roads readings. 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 <= 1584; 0 <= m <= 1584.

Example 1:

Input: 1176 356 638 794 962 1053 6 756 560 633 79 338 567 635 347 522 520 931 472 1014 571 573 425 443 197 1107 872 1171 101 925 401 852 368 451 122 185 656 916 174 192 250 761 4 954 283 467 447 1147 742 1149 694 708 192 779 33 592 285 438 257 284 196 603 76 742 530 1154 441 842 518 991 201 821 912 1008 38 1073 139 1109 312 766 600 1083 757 1107 115 783 223 645 698 1158 353 676 250 826 29 112 378 1065 207 852 423 462 338 884 504 610 421 1155 429 935 153 466 421 522 112 819 190 881 689 1011 889 901 1125 1127 431 1130 464 476 523 886 563 909 103 983 102 518 178 340 587 1019 44 367 244 917 78 781 885 986 312 821 629 1175 209 602 362 1091 220 1039 175 399 428 493 825 1010 687 1007 690 793 307 329 319 359 357 634 206 1032 402 1047 375 854 16 206 310 559 105 636 68 382 931 946 51 1069 222 478 214 914 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: 813 936 283 492 538 560 16 686 88 252 269 811 252 623 323 467 62 251 162 735 350 716 483 766 360 367 310 467 589 626 177 498 2 654 510 671 172 400 433 780 284 791 213 371 37 780 347 729 74 471 237 808 126 315 234 684 565 684 143 505 63 123 67 732 251 699 326 731 21 707 201 235 38 535 267 693 75 245 582 776 156 415 18 148 345 777 358 390 499 633 441 645 33 512 91 568 265 614 85 112 417 606 419 756 469 577 188 547 169 634 346 731 48 664 275 681 632 747 374 698 135 812 172 416 115 308 285 370 98 464 45 497 456 732 240 575 81 130 427 642 263 767 53 399 589 762 538 620 234 436 367 591 55 463 548 690 187 796 123 722 297 780 125 199 341 363 305 646 207 431 77 533 192 704 100 228 275 347 3 712 456 561 189 298 602 749 119 629 315 369 401 609 419 721 544 589 126 259 332 690 34 368 191 232 434 669 15…
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: 1263 981 58 403 54 152 169 796 314 1040 213 505 218 513 850 1149 131 714 710 1061 857 928 629 853 275 360 567 1161 790 1103 778 923 85 399 432 929 545 943 417 1080 684 806 509 1070 161 994 248 618 380 701 109 905 825 881 48 657 43 1249 144 1252 374 798 283 590 339 340 464 777 566 1056 352 452 34 1019 251 771 53 461 495 534 16 600 44 575 452 784 804 870 41 216 112 166 1068 1082 486 754 134 1183 283 567 751 875 511 665 222 310 154 855 92 1066 157 1136 588 637 1017 1220 532 855 572 826 137 298 30 797 52 1227 152 974 527 1047 31 968 202 1060 78 1081 195 1045 842 1098 276 402 660 708 625 802 569 824 565 718 268 647 340 531 1199 1202 285 707 804 1088 585 740 454 496 874 1204 236 663 577 1247 616 703 58 848 410 877 888 1061 187 917 641 1022 604 1191 239 750 769 1097 44 964 845 1120 653 861 390 76…
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 <= 1584; 0 <= m <= 1584.

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