CT39470

Anaya's Ledger of routes

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Anaya the archivist watches over the coral atoll of Pearldeep's stores of routes. A careful computation stands between order and chaos. 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 <= 3886; 0 <= m <= 3886.

Example 1:

Input: 3134 1029 44 1450 632 2784 562 1534 2403 2527 623 714 410 1422 1883 2614 132 2048 743 985 2078 2775 2571 2964 1766 2755 809 1744 1350 2391 1670 1935 1119 1710 298 2937 312 1156 263 2622 850 2867 1882 2177 61 1987 2297 3126 256 2975 829 2149 1491 1739 142 1276 1135 3116 642 2596 319 2092 1778 2616 1585 2481 39 1799 2608 2743 503 2917 705 1921 79 1896 195 2633 1379 1492 2429 2947 1551 2548 942 1428 584 944 1024 1876 1438 1498 574 1580 1802 2284 24 699 243 351 855 1312 491 2594 1434 1628 1063 1227 1236 1395 1529 2610 565 2608 1264 2833 502 779 481 712 476 2506 1519 1801 193 3071 98 2968 1094 1291 1770 1921 343 3044 300 880 2165 2610 1529 1939 1740 2902 2852 3044 357 2211 1214 1407 1354 2845 1666 1681 1366 2399 2434 2684 1792 2900 250 1416 2318 2756 2026 2937 2138 2343 1247 2938 1068 2584 2109…
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: 1990 2123 548 992 1607 1814 268 1580 634 1860 1503 1537 219 1734 1714 1928 851 1538 339 955 167 1491 1050 1290 1803 1804 214 1325 310 632 241 1746 126 381 601 1773 1029 1472 351 1640 444 1352 98 524 367 1971 381 1629 595 1155 484 1482 776 1145 499 1853 1227 1459 861 975 1348 1437 1267 1909 843 1111 1298 1905 16 348 1433 1711 983 1398 459 1710 277 1810 209 879 1122 1188 229 1022 527 1744 1169 1562 720 1068 211 1045 463 1048 260 1085 1311 1696 380 1818 425 1240 369 1156 393 1591 134 728 1042 1357 98 1536 1247 1460 211 1290 164 1938 421 542 65 291 504 1357 941 1625 978 984 49 1419 793 1852 59 982 712 1898 867 1210 1301 1744 1120 1224 847 1134 450 716 721 885 1308 1985 236 503 772 1742 295 1729 628 1829 1199 1968 281 1899 1002 1504 866 875 452 1986 1478 1632 274 1916 201 473 1089 1434 1374 185…
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: 1090 2597 944 985 668 1065 190 1057 399 728 74 736 547 590 415 677 748 1055 263 566 602 909 63 584 579 750 67 953 425 1027 619 688 12 442 278 376 863 959 935 994 454 597 377 660 315 407 329 890 698 916 240 466 488 833 225 584 279 981 396 920 289 1063 478 1065 313 800 439 684 322 882 549 616 36 1071 334 898 176 550 613 866 185 537 317 596 399 825 6 257 691 964 423 591 615 986 158 498 199 849 321 812 745 801 582 776 414 902 476 958 650 1059 871 989 189 201 27 699 105 909 82 630 516 614 563 711 108 789 697 985 775 807 518 1082 289 578 399 1014 8 1069 109 174 294 824 788 1048 53 652 715 751 559 833 614 1065 282 655 276 794 137 738 164 649 379 409 617 628 131 222 633 818 94 1080 102 367 168 285 45 724 532 721 97 642 1040 1068 429 861 291 571 213 261 452 709 492 538 283 425 208 293 732 806 1054 …
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 <= 3886; 0 <= m <= 3886.

Loading...
Test Cases:No test cases
No test cases available.
Anaya's Ledger of routes - MEDIUM Coding Problem | CodeTikki