CT40975

The Build Order of Misthollow

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Morning light hits the valley of Misthollow as Nora unrolls the day's manifest of bridges. The tally will decide the next shipment. 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 <= 2495; 0 <= m <= 2495.

Example 1:

Input: 2202 940 72 1848 1135 1412 1122 1165 861 1999 1325 1702 467 1159 145 552 1646 1702 1735 1801 436 547 24 277 751 1961 1285 1463 1233 2121 329 1152 465 1384 983 1146 421 1102 1216 2116 976 2095 422 975 750 1099 1667 1785 757 1049 657 2016 56 1782 637 909 996 1120 632 1372 499 785 510 1624 1201 1443 310 1394 155 667 1123 1361 559 857 1830 2200 528 802 170 607 547 2199 567 1523 1121 1583 169 766 191 939 190 1875 1285 1768 1032 1154 846 2126 496 518 740 1924 781 1488 1421 1677 799 1913 43 2182 48 1247 545 554 2 1519 1731 1789 789 2068 52 2135 1536 1571 448 1182 729 850 1611 1920 393 788 116 1382 421 2064 886 1018 433 621 747 1366 915 1235 1745 2185 236 1167 695 1007 639 1093 796 1434 402 417 1025 1907 153 1804 983 1622 588 1375 1326 1420 336 1415 94 603 370 1731 636 754 1511 2110 1537 1973 698 …
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: 1173 877 154 1108 180 873 428 810 55 795 435 482 40 91 106 906 204 1003 176 1029 824 961 696 935 720 892 5 876 148 624 733 1052 37 987 290 725 265 313 619 757 608 833 117 941 199 893 187 388 768 794 718 1050 678 897 55 906 823 1055 200 590 349 1007 746 938 58 143 374 655 875 965 237 1147 359 384 862 865 625 858 478 628 279 777 80 989 281 567 3 967 574 1021 888 912 82 320 360 831 314 952 1 850 234 580 88 443 460 836 165 524 954 1063 166 713 458 1072 880 970 420 1053 104 662 454 690 698 993 167 494 719 1129 731 1061 15 778 552 1031 226 241 225 318 218 1042 501 1098 132 1145 569 668 839 1003 357 392 52 326 747 1013 587 1115 208 542 712 883 936 1094 649 794 519 880 132 949 263 429 30 1087 249 641 36 708 393 437 361 545 42 879 697 1126 269 1117 544 1063 820 994 1122 1159 632 661 151 514 714 112…
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: 794 1148 248 590 129 744 220 775 446 790 219 382 229 664 44 425 160 794 127 194 374 654 177 564 720 729 321 718 642 651 277 705 711 712 692 740 534 754 139 391 13 89 519 577 68 152 183 192 560 667 13 112 428 493 95 207 183 586 204 420 91 784 68 286 568 672 250 765 256 534 337 470 452 709 458 539 168 678 534 578 308 543 207 658 102 332 30 508 61 145 318 485 406 598 102 381 350 388 17 154 461 500 436 631 129 496 37 129 651 701 39 368 201 303 480 546 373 455 351 678 351 461 161 516 315 698 388 568 410 766 308 340 1 602 211 533 6 693 57 99 241 315 411 475 311 323 56 488 81 630 359 760 735 782 542 675 301 490 160 272 337 435 110 757 9 201 482 594 454 675 319 765 313 673 433 501 80 441 153 301 409 492 273 422 16 714 646 704 36 152 78 310 49 545 487 498 307 338 80 99 345 589 41 562 31 453 162 288…
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 <= 2495; 0 <= m <= 2495.

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