CT43217

Last routes of Ranger

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

The harbor bell rings at the cork grove of Barkhaven; Ranger weighs the day's routes manifests and starts the calculations. 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 <= 3004; 0 <= m <= 3004.

Example 1:

Input: 2509 1466 172 439 2155 2403 596 2344 1488 2308 1798 1894 1446 1756 1652 1747 16 671 106 547 230 1111 1928 2033 2152 2340 2162 2302 297 2443 72 1508 2135 2491 555 1132 1020 1522 139 853 339 2154 1205 2225 1499 1980 326 601 384 2202 310 1391 1368 1399 571 1614 1301 1486 1192 2183 1959 2148 944 1044 1010 1013 543 2042 870 963 116 147 1696 2026 592 1153 369 960 831 2101 125 1748 820 2065 102 1731 310 1232 822 2382 242 1410 1185 1351 826 1294 761 1599 1234 1414 2244 2449 1569 1781 915 2271 1040 1097 1807 2487 27 90 479 2312 560 2060 845 908 747 1743 273 1151 258 1949 1003 2032 478 1421 483 860 382 825 987 1471 190 2392 258 1083 1306 2255 949 1514 476 539 477 1059 872 1948 1859 1892 45 1398 994 2004 108 1683 967 2345 161 1593 765 1377 331 1803 175 999 329 559 790 1507 868 1119 2230 2288 903 2053…
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: 1982 1604 1308 1934 68 1951 63 645 120 578 1640 1933 1248 1597 1885 1980 1859 1906 1226 1400 164 1042 575 1193 125 607 314 1953 105 1387 1477 1601 235 1928 865 1859 365 641 573 1317 1575 1714 1862 1964 3 631 304 1389 1292 1675 6 924 209 980 1546 1621 932 1535 1186 1611 96 765 1014 1932 1296 1482 256 794 1044 1688 523 1939 77 1576 1462 1837 634 691 569 864 818 1760 1378 1630 130 1438 1557 1587 22 624 834 1425 1254 1374 723 804 139 435 979 1113 520 733 148 1969 398 1538 746 957 678 833 995 1428 1780 1892 1462 1863 578 1418 1031 1074 46 1735 905 1737 843 1913 988 1221 603 1290 393 509 1307 1975 421 1389 283 1031 117 881 872 1517 1148 1878 1050 1417 137 997 572 627 940 1236 421 1723 806 1355 1168 1391 717 1151 1815 1868 947 1773 1106 1212 531 1524 76 548 487 1228 37 1586 194 1210 1143 1860 157…
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: 21 96 19 20 9 14 5 19 14 15 15 17 6 7 17 21 13 17 3 11 8 13 6 10 2 6 1 14 13 14 11 12 5 11 9 20 6 18 6 16 4 10 8 14 8 15 2 5 9 12 17 19 16 20 7 19 13 15 14 16 1 15 5 20 8 21 2 18 4 20 7 10 6 9 17 18 2 7 1 21 3 16 1 7 1 12 5 14 8 16 12 14 16 21 11 15 5 9 1 10 2 21 20 21 15 18 1 6 2 8 6 14 5 18 4 9 7 8 3 4 4 7 15 19 3 12 9 10 10 17 1 16 2 12 3 5 3 9 12 13 9 17 6 13 18 20 3 21 4 19 13 19 5 16 10 18 4 12 2 13 4 21 9 11 7 13 6 12 15 21 6 17 10 13 11 19 13 21 5 13 4 15 4 11 7 18 10 19 12 16 7 11 7 15
Output: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

Constraints:

1 <= n <= 3004; 0 <= m <= 3004.

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