CT50788

The Build Order Beneath Mirrormere

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Cobbler found an old ledger of canals in the boathouse attic at the lakeside town of Mirrormere. The margin notes pose a precise question. 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 <= 1374; 0 <= m <= 1374.

Example 1:

Input: 109 1195 82 101 11 74 75 76 5 58 47 67 44 107 32 79 47 70 12 75 25 42 23 108 28 85 2 80 99 105 5 85 33 46 70 81 20 36 47 51 22 83 87 94 32 94 18 34 21 34 6 63 38 83 1 66 37 47 23 35 101 105 58 103 13 53 40 92 14 44 12 73 40 99 91 97 77 96 77 97 16 42 64 107 56 83 2 35 64 68 5 49 14 85 60 100 24 67 94 108 20 68 16 22 69 71 25 68 19 92 12 92 69 73 10 101 26 40 52 60 25 58 105 109 29 52 25 51 77 109 43 82 15 34 3 62 24 36 88 108 6 14 1 9 9 108 83 98 53 78 37 100 11 41 52 105 21 74 11 53 74 97 18 49 52 56 27 81 51 54 3 53 53 98 7 78 30 62 12 37 25 89 93 102 73 103 41 77 53 94 8 91 38 65 20 67 21 89 59 71 9 105 24 96 76 86 25 79 2 88 49 94 30 100 24 54 29 67 54 83 2 82 28 68 46 70 26 82 43 107 21 35 39 91 8 36 56 98 39 65 22 99 37 87 13 95 15 35 15 77 2 21 22 30 68 76 55 80 103 106 14 27 61 72 …
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

Example 2:

Input: 848 147 458 687 541 613 263 568 643 830 196 202 456 847 98 372 132 532 287 713 303 488 53 219 93 461 120 733 174 617 180 542 526 779 562 784 431 491 87 774 191 246 396 636 162 333 398 710 202 641 564 824 233 248 401 816 640 818 348 367 153 257 552 666 388 615 144 757 459 649 513 598 288 560 381 827 150 648 253 487 90 440 717 821 205 773 39 723 170 809 31 262 80 745 38 689 415 520 205 592 31 331 96 210 217 534 103 182 415 724 262 509 585 818 280 483 257 340 21 835 449 599 187 240 159 415 338 622 103 780 151 520 226 493 420 613 286 512 685 737 633 795 285 622 455 684 322 523 14 726 468 613 266 786 538 561 30 406 30 220 39 220 288 321 49 287 338 735 632 794 110 363 282 342 224 803 525 545 520 777 701 843 533 688 173 425 662 804 532 664 399 551 235 511 572 634 119 538 285 732 51 537 119 396 12…
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: 1252 111 701 1008 1064 1132 10 11 246 838 329 1134 246 630 472 614 56 416 197 643 897 999 3 874 395 457 137 1085 639 722 408 906 298 734 934 1117 575 1029 490 520 887 995 152 995 980 1115 99 1100 918 1226 401 483 216 1233 552 1178 14 956 536 1166 386 639 677 806 411 659 272 868 73 1215 306 796 179 507 591 995 433 824 717 719 202 768 108 322 381 1251 204 507 232 1090 143 1059 866 1027 698 1059 828 895 589 1213 283 505 457 589 615 1123 318 569 209 600 454 561 670 1087 278 344 288 359 318 731 962 1087 937 1069 1067 1116 544 663 452 1241 636 1192 240 560 831 1101 396 856 629 922 21 956 92 1119 490 735 382 1148 367 1107 12 468 304 934 736 793 144 510 301 1204 495 886 703 1120 246 392 378 1212 57 962 198 547 651 838 22 612 657 892 101 154 438 748 56 547 485 840 525 796 405 983 397 570 717 1083 4…
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 <= 1374; 0 <= m <= 1374.

Loading...
Test Cases:No test cases
No test cases available.
The Build Order Beneath Mirrormere - MEDIUM Coding Problem | CodeTikki