CT64790

Rune and the Verdant routes

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Rune found an old ledger of routes in the brewery attic at the otter slides of Sleekwater. The margin notes pose a precise question. 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 <= 2969; 0 <= m <= 2969.

Example 1:

Input: 1932 126 924 1603 149 1671 1358 1471 369 1434 19 1909 723 1136 92 938 1336 1393 1065 1801 1169 1362 1668 1792 1012 1657 1086 1152 1056 1892 622 925 1485 1787 301 1221 36 522 1581 1704 1673 1786 264 642 589 1730 943 1777 932 1305 906 1162 448 1199 78 1239 339 1897 210 436 682 1613 644 1446 954 1862 358 1818 1087 1888 797 995 70 1342 70 1414 1049 1112 742 752 773 1525 1137 1700 192 1276 1306 1383 548 1520 263 1319 659 1786 282 895 192 772 104 961 191 1357 748 1419 831 1107 221 1835 734 1906 811 822 82 163 672 939 448 988 774 1888 416 1869 478 1002 601 1679 591 1540 24 172 624 1408 169 1474 36 1487 1102 1241 108 476 191 458 923 1160 111 213 840 1678 14 377 136 1177 407 1911 839 1055 123 402 114 930 886 1735 735 743 944 1591 445 885 60 1252 125 1600 801 1760 1140 1912 384 1468 724 1631 45 482 …
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: 1038 1680 335 408 808 932 241 260 298 637 271 865 173 795 195 290 94 860 674 823 522 606 28 423 659 761 749 836 246 478 275 986 747 1021 10 477 200 408 290 583 362 671 317 632 446 1013 818 1031 135 514 122 232 726 798 73 995 636 875 543 930 27 901 165 739 198 498 210 981 73 765 736 860 332 652 693 830 886 924 573 836 1 22 206 831 514 632 39 926 50 684 276 599 427 532 149 327 691 1030 488 643 141 973 104 698 109 996 313 463 379 714 465 640 743 874 867 935 105 825 441 1003 4 60 484 777 472 517 702 909 223 563 61 424 416 985 686 1001 261 879 862 1002 397 919 56 151 924 997 802 872 139 736 21 142 59 755 317 519 36 870 87 1003 937 1025 566 642 476 640 286 439 558 1025 718 988 63 415 539 562 255 539 790 953 589 681 255 788 112 496 617 1017 606 867 393 630 143 297 99 366 163 603 639 934 98 477 35…
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: 2336 1558 64 2240 517 1077 689 1505 261 370 1412 2159 1213 2022 263 2257 327 1489 1105 1166 866 1371 817 899 749 831 235 1850 192 830 634 2135 920 1521 677 962 983 1617 673 1726 868 2148 1357 1933 938 1766 69 1095 331 1964 1274 1280 897 1532 2051 2321 1596 1618 839 1806 439 1169 341 1509 830 894 116 1485 367 1735 1200 2188 2001 2170 1042 1839 1995 2052 555 1833 557 2323 1554 1972 4 1905 228 1220 1452 2317 1330 1986 90 1844 942 1051 320 570 2029 2060 597 1614 768 883 65 1415 161 2090 1637 1752 328 883 1421 1773 960 2170 310 1892 1275 2265 1116 1778 212 1405 1863 2000 267 1891 140 2215 651 1938 948 2048 2058 2178 159 1559 91 228 1142 2310 812 1927 681 796 631 1685 833 2182 1147 1622 2245 2272 654 1278 1504 2306 1235 1916 227 471 627 955 153 770 297 890 947 1752 1411 1890 860 1284 626 660 522…
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 <= 2969; 0 <= m <= 2969.

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