CT50001

Last routes of Navigator

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Before the gates of the kelp forests of Tangledeep close for winter, Navigator must finish the routes ledger - one figure at a time. 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 <= 3508; 0 <= m <= 3508.

Example 1:

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

Example 2:

Input: 3132 1982 1000 2870 933 981 816 1866 859 1087 1903 2339 827 2076 1838 2875 1249 2084 325 2642 1003 1371 1 1962 615 1123 464 675 2398 2490 2622 2754 265 493 917 1724 192 561 1504 1700 780 3080 1511 1657 955 2434 516 1567 1658 2570 647 1445 610 1070 1633 2517 1658 2069 1500 2834 1712 2780 916 2714 336 2611 1821 2687 795 1728 502 2515 197 1619 1855 2066 1164 1811 1081 2789 324 643 220 1465 867 1052 1795 2878 1321 2289 1439 2615 1085 2061 2152 2744 534 1863 1416 2731 1720 1839 853 2353 669 1783 2264 2526 1111 1725 849 1151 1627 2919 2598 2856 925 1515 528 917 1381 3124 1556 2420 501 1755 437 1541 2750 3043 2192 2431 787 1522 2363 2916 313 546 692 2352 1628 2500 1726 2799 825 2423 270 1417 386 1954 538 1467 825 2620 736 1969 2904 3065 1409 2255 540 1228 1257 1848 93 1743 2578 2774 2389 2532 146…
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: 1552 66 64 1411 468 500 375 912 827 1550 920 1287 590 1545 742 963 446 1148 659 1129 333 843 927 1000 574 1545 216 536 23 526 672 1516 213 1054 550 1417 310 1128 682 1020 906 1385 620 1505 566 1213 722 947 869 1134 361 749 470 1475 1167 1469 366 1328 255 309 4 451 1360 1512 705 1042 503 1537 151 493 893 1301 35 143 35 536 942 1146 96 1390 312 1520 493 1233 485 804 62 1337 464 635 629 817 56 79 246 1038 806 999 430 1237 296 920 978 1522 476 561 753 1534 326 733 135 693 676 1013 202 361 399 1505 1164 1441 543 594 868 889 750 1488 199 871 535 915 574 755 811 1111
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 <= 3508; 0 <= m <= 3508.

Loading...
Test Cases:No test cases
No test cases available.
Last routes of Navigator - MEDIUM Coding Problem | CodeTikki