CT37540

The canals Build Order Puzzle

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

The council of the crystal caves of Luminar pays by the answer, and Zane intends to earn it. First: the full register of canals. 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 <= 3252; 0 <= m <= 3252.

Example 1:

Input: 1583 2441 509 1297 279 844 1069 1345 76 280 719 1541 204 1580 580 1563 596 1116 444 1123 91 667 442 553 327 370 36 1099 1261 1421 1025 1244 968 1335 1038 1381 628 1213 1146 1342 725 794 5 1494 410 1365 517 1571 828 1171 330 1353 864 1039 1165 1227 966 1073 913 1083 402 1261 1282 1381 791 1392 1232 1371 212 335 485 670 866 1107 463 477 1017 1457 1032 1541 68 779 656 1571 371 658 924 1004 234 839 279 1526 96 1281 21 947 683 847 488 685 593 1165 1085 1540 913 1230 642 1112 840 1461 1129 1583 255 998 876 1200 384 1149 63 287 779 1572 279 1125 146 602 465 1340 461 1118 67 1045 34 1437 328 1214 574 611 1110 1376 54 230 796 894 130 1069 291 1039 209 1017 497 1392 274 853 517 1238 360 1311 67 1421 59 396 56 181 369 851 1029 1550 498 1189 449 1014 282 1439 291 738 925 1044 799 1502 40 440 1049 1330…
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: 863 2366 221 839 252 329 567 786 525 699 321 537 309 614 211 653 453 609 135 559 535 790 778 826 56 286 19 430 680 717 525 707 499 673 595 758 404 834 326 381 46 144 323 616 14 236 130 702 412 584 554 810 55 670 366 628 303 641 446 740 600 838 274 570 198 649 618 732 819 852 4 26 34 115 77 405 10 472 239 459 146 227 266 541 78 527 612 798 528 676 16 682 412 510 31 125 142 353 355 654 251 742 161 164 39 823 156 501 412 714 189 757 156 254 31 218 469 516 36 543 521 763 152 200 105 652 82 274 121 231 40 284 567 749 24 613 120 799 670 703 245 697 88 581 439 645 85 735 399 851 673 777 670 745 29 703 106 508 222 805 252 722 349 860 731 741 587 838 448 784 573 664 168 296 580 692 482 860 191 828 347 519 298 537 235 535 417 526 100 563 129 601 353 642 9 311 7 602 42 501 270 325 133 339 471 775 290…
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: 2802 935 328 912 771 2642 306 1162 102 1382 12 285 797 1163 989 2614 772 1120 1190 1213 2284 2726 493 558 68 2188 680 2072 672 2050 1559 2334 177 597 1275 1897 1845 1877 800 2030 1047 1790 276 2304 560 2712 236 745 801 2157 1868 2420 584 1398 1715 2456 1001 2145 761 802 1171 2342 1005 1575 1708 2518 1412 2243 521 2501 1843 2053 980 1779 1049 2704 1814 2433 239 839 985 1821 18 856 287 2369 396 2684 1452 1516 1474 2003 2268 2462 1990 2063 2 2486 607 1610 176 1918 1446 2114 388 945 2164 2646 140 1257 1975 2627 58 74 46 700 105 1105 18 1483 148 731 1095 1939 897 1252 1038 2446 1681 2393 1365 1619 537 1533 1420 2762 2309 2563 534 1829 956 1841 1126 2755 1049 1902 1655 1867 294 2425 1088 2384 1296 2000 52 1242 1021 1999 1393 2067 1083 2669 1735 1920 878 1965 30 2513 531 613 349 2599 1194 1702 10…
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 <= 3252; 0 <= m <= 3252.

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