CT50411

The Build Order of the Woven corridors

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

In the glass towers of Prismhaven, Cora the customs officer keeps careful count of the corridors. Prepare the expedition manifest, every figure matters. 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 <= 2364; 0 <= m <= 2364.

Example 1:

Input: 809 1655 8 484 234 546 116 448 444 584 67 759 582 653 10 89 41 55 200 552 166 619 572 796 69 166 4 430 789 803 22 609 209 598 17 138 103 410 83 781 436 619 144 435 215 657 69 128 133 596 14 171 436 633 331 626 185 589 301 785 312 478 312 338 398 403 428 587 517 571 153 479 546 582 168 175 107 479 499 515 437 653 220 429 150 526 122 179 43 554 718 720 6 270 129 448 151 583 158 797 354 421 493 606 184 588 114 133 252 322 341 417 654 719 57 701 4 781 197 615 215 626 498 516 159 807 111 606 6 393 141 703 87 334 37 391 371 462 202 495 174 533 469 559 780 783 282 786 9 595 344 675 21 587 270 480 437 725 3 469 158 493 413 772 117 741 30 385 88 412 105 126 477 482 240 793 262 512 463 752 63 198 464 721 123 596 26 331 167 172 6 447 50 751 254 618 356 403 151 780 3 809 91 224 392 584 220 448 349 730…
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: 1135 2199 800 969 81 262 272 466 600 940 68 377 640 747 434 941 338 733 234 795 841 1132 543 899 451 1044 40 483 10 87 762 959 872 1054 873 906 1031 1131 365 566 204 638 262 324 468 569 86 483 606 1055 26 221 209 1008 557 680 546 1129 464 958 590 849 293 396 308 454 550 769 263 792 18 1120 165 591 488 964 150 836 148 1001 728 969 871 1027 615 729 317 514 659 849 623 894 609 1095 632 708 245 334 400 481 683 790 201 637 305 1034 180 422 29 606 252 822 246 415 210 809 203 380 59 847 414 1121 670 872 258 803 506 856 8 287 3 1028 427 894 584 1035 805 959 44 676 135 163 57 738 645 974 838 845 93 862 556 1102 128 728 957 1068 266 1098 766 1060 279 657 674 1093 297 512 96 352 196 576 104 1107 433 946 420 1000 593 834 698 1055 511 540 67 724 503 733 439 826 82 139 119 268 324 370 993 1024 80 541 48…
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: 1619 69 377 1618 61 124 86 1109 333 1610 236 565 1120 1517 922 930 1277 1516 149 1255 1034 1433 694 1031 686 798 933 1597 225 734 741 1417 75 366 255 1315 803 1484 794 824 93 606 214 1406 119 1138 466 828 1199 1499 402 522 21 759 425 957 200 581 929 1034 820 869 541 1351 387 1100 767 1300 642 720 1279 1607 622 1240 72 1068 126 1126 543 971 197 1214 281 673 283 403 345 720 906 1448 164 1124 442 1075 540 1535 812 1114 207 944 1470 1605 664 783 1019 1126 915 1152 153 1020 819 1530 157 678 465 824 653 1066 74 240 509 1266 32 1276 26 871 191 908 128 669 34 890 346 1411 533 1546 613 1468 752 1267
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 <= 2364; 0 <= m <= 2364.

Loading...
Test Cases:No test cases
No test cases available.
The Build Order of the Woven corridors - MEDIUM Coding Problem | CodeTikki