CT64656

Elowen's Ledger of tunnels

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Every season at the island market of Coralcove, someone must track down a clerical error. This year the task falls to Elowen, armed only with the tunnels register. 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 <= 2600; 0 <= m <= 2600.

Example 1:

Input: 1205 124 546 965 129 494 154 1044 931 1066 524 541 795 1139 125 1076 462 1081 1097 1176 801 1130 159 401 24 869 226 585 210 832 1003 1068 872 888 101 391 631 727 715 906 10 274 341 666 63 157 12 658 554 1104 87 879 362 597 146 261 21 610 341 699 139 557 111 552 484 943 630 681 208 639 971 1171 988 1057 452 1149 583 954 548 946 397 573 107 808 421 504 44 986 82 678 549 1064 589 1101 16 751 187 722 420 804 166 855 664 1024 627 886 432 683 419 903 653 1039 430 737 209 521 147 492 205 1115 569 680 505 920 713 1012 546 1027 160 440 200 606 64 516 76 242 955 1008 88 201 954 969 225 572 485 1107 270 909 396 1191 29 82 718 742 505 1146 400 684 513 937 288 583 671 902 400 1129 259 596 772 966 213 1010 707 1096 357 958 96 955 94 863 214 802 478 1081 190 930 185 1146 919 1120 578 786 295 368 688 1184…
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: 2307 2132 879 1915 1907 2131 1087 2244 422 1136 692 936 923 2151 430 1692 649 1793 53 1223 775 1150 844 1322 721 1126 1396 1701 1650 2003 384 511 1521 2095 187 1805 342 1371 1786 2267 362 1320 202 570 82 1223 1197 2170 1100 1534 1716 2085 809 866 775 933 21 97 1353 1567 947 1066 24 1121 637 1890 91 899 398 438 171 1838 358 1532 1048 2278 656 664 647 2217 415 1467 399 2148 7 1268 1397 1815 873 1993 247 416 859 1173 1032 2109 993 2092 1397 1617 440 1241 149 2081 1066 1636 155 634 1208 1618 27 293 1529 1717 653 833 1738 1918 1331 1920 1770 1797 1092 1273 180 556 776 2150 1905 2299 547 1493 510 1992 222 980 162 1528 1546 2001 1274 1634 1162 1796 865 1725 1071 1521 60 910 171 2052 1352 1715 658 1702 191 538 11 294 1538 1838 1901 1944 760 878 1894 2067 416 1278 271 712 508 1076 332 977 1180 1801…
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: 2046 687 872 1915 784 1093 712 1379 42 1768 46 95 562 1210 213 1254 101 1265 1154 1329 577 1976 158 1464 65 1126 629 1326 4 1019 1312 1827 113 765 97 1978 130 1194 870 1969 515 830 1201 1802 1136 1619 79 972 83 340 793 970 1531 1574 1730 1799 12 1876 78 878 63 213 840 942 233 1073 128 926 42 866 980 1249 378 820 1491 2036 426 685 261 1742 1351 1635 463 1604 1129 1270 821 1785 1249 1322 105 1053 116 286 1205 1272 190 1252 608 1081 92 1595 53 1690 17 1352 737 1935 548 771 67 1345 47 1807 89 389 1730 1828 483 1872 825 2034 572 999 549 1035 759 1033 1001 1499 222 1362 1082 1334 400 959 436 647 32 177 1511 1625 800 1340 379 508 162 363 1193 1682 319 758 548 1225 381 403 879 1211 860 1237 1037 1384 147 1893 151 467 179 1081 1373 1951 424 1091 420 868 593 796 166 1822 996 1974 878 1568 122 705 78…
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 <= 2600; 0 <= m <= 2600.

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