CT55743

Faded routes Build Order

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Legend says the vault under the desert outpost of Sandspire opens only for a perfect tally of routes. Quartermaster means to find out. 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 <= 3049; 0 <= m <= 3049.

Example 1:

Input: 1860 1608 1324 1746 409 1430 806 1098 38 1510 895 1454 1623 1644 359 473 55 1508 1583 1609 1060 1253 365 834 1095 1726 412 1079 1033 1276 427 1854 915 1153 454 1654 1518 1565 378 1210 669 1203 682 1302 414 1258 10 913 487 1108 159 1569 1215 1837 1174 1498 270 1165 660 1291 1292 1593 352 922 923 1810 237 547 606 1069 84 1120 979 1155 651 1201 27 883 192 1763 59 382 103 936 1481 1495 501 1727 659 1591 404 609 671 836 1342 1626 439 599 66 362 256 1525 622 1813 834 1205 94 207 515 1816 22 726 43 1166 295 718 30 850 235 1480 1600 1659 353 408 926 1671 732 1302 1589 1718 555 1336 104 1476 601 1508 150 484 150 881 285 1609 1333 1449 411 614 1526 1730 311 1232 1221 1832 44 680 193 1747 451 1158 615 958 44 981 8 885 967 1548 789 795 119 721 603 1533 777 1230 715 1300 400 1673 291 1349 605 1546 1038…
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: 1096 1468 57 412 843 1061 399 900 203 1054 145 765 131 1081 249 862 82 839 841 998 741 1089 336 532 380 604 21 716 88 151 10 195 344 940 206 529 673 997 327 371 470 840 459 494 265 417 580 620 566 965 333 420 823 1075 303 676 279 939 159 853 550 936 681 702 120 876 214 286 949 1088 782 999 204 337 229 1008 781 876 21 592 19 230 148 248 342 595 155 894 598 889 149 482 387 518 39 266 38 71 538 724 334 346 495 1014 367 406 32 1066 35 888 460 996 338 607 485 790 407 877 225 869 350 804 70 198 82 924 171 851 123 549 552 652 122 741 257 774 283 915 196 691 73 112 556 630 632 841 510 774 414 876 768 1086 296 941 526 1040 224 826 708 788 32 1054 129 195 647 1037 332 581 797 1046 826 981 82 780 579 583 447 863 596 726 23 76 128 414 411 686 505 935 612 627 341 449 180 299 290 1081 820 1003 282 927 5…
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: 2965 2680 1823 2709 946 1408 243 1220 794 2381 2086 2389 1777 2685 165 546 27 2817 877 2892 126 2240 485 2533 54 361 2072 2400 1376 2541 900 2319 361 1908 1643 2190 1602 2269 2023 2410 297 1919 1536 1702 1386 2042 984 2024 560 2486 1580 1684 776 2227 681 788 2430 2738 1256 1747 491 1237 1675 1840 1210 2132 536 2528 706 2820 937 2540 1890 2822 273 2626 450 2597 406 906 2093 2264 2073 2276 1070 1726 572 747 131 887 2466 2867 503 2176 1991 2496 1767 2204 247 276 896 1266 1473 2147 530 1181 136 798 704 2168 1863 2656 1762 2152 1928 2402 997 2045 1055 1246 812 2640 558 2088 65 2287 1312 2441 1183 2130 398 1522 428 1834 413 2204 172 1700 1822 1893 665 1206 653 1463 1140 2377 1569 2403 2457 2762 1048 1921 206 656 1417 2902 184 1510 1524 1597 274 420 2446 2707 2842 2869 140 753 856 2153 1509 2118 …
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 <= 3049; 0 <= m <= 3049.

Loading...
Test Cases:No test cases
No test cases available.
Faded routes Build Order - MEDIUM Coding Problem | CodeTikki