CT46326

The Verdant tunnels of Ivo

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Ivo inherited the salt store at the port of Emberfall along with its curious bookkeeping system for tunnels. Time to make sense of it. 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 <= 3826; 0 <= m <= 3826.

Example 1:

Input: 2880 1695 140 2771 363 1221 721 906 332 2630 2011 2264 1619 2557 787 930 14 2413 1147 2189 828 2417 409 1805 370 2454 2044 2739 103 2287 153 1518 125 2746 1964 2242 989 1631 517 596 1252 2517 1517 1603 2251 2761 384 1436 31 1360 301 1791 696 2616 113 833 134 1087 945 1461 752 777 226 2479 2216 2522 196 2533 1035 2101 1315 1821 233 738 688 2608 79 2740 1092 1648 280 2457 216 1761 693 802 919 1676 887 2394 1551 1592 2067 2623 375 2558 924 1288 256 1588 106 1675 363 1199 1399 1728 787 941 875 1647 1919 2867 534 2462 1565 1910 302 1125 1816 2444 324 2638 670 2700 1419 1804 407 2012 634 1115 1298 1713 658 2837 1675 2672 2018 2833 865 2026 127 2835 490 2114 533 2631 1676 2312 1528 2652 109 2375 884 967 1564 2501 525 2128 1121 2256 496 733 794 1267 1607 2780 1789 1898 1636 2569 1630 2212 695 2505…
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: 3038 2229 2084 2183 2050 2422 105 840 1676 2487 76 2034 1045 2660 689 1980 441 1787 862 887 8 40 2595 2962 2191 2679 138 1223 341 556 501 1760 1817 2410 1289 1884 719 1618 1965 2254 1411 2618 601 2058 65 1559 2282 2403 1746 1753 983 2377 504 2153 514 2404 596 1288 1461 3033 719 1373 1794 2635 123 531 524 1521 280 885 325 2032 90 644 456 2675 751 843 2312 2314 1037 2106 868 2439 242 1686 2002 2871 354 1002 363 2415 1504 1957 670 2987 59 692 536 1802 1743 1795 1919 2568 103 1491 1095 2394 212 967 1486 2250 2280 2826 166 2751 691 1908 1287 2753 817 1862 960 2247 251 2356 1012 1149 1197 1249 1640 2554 1147 2697 1114 2831 374 2317 1309 1962 2110 3017 475 1843 941 1396 412 852 509 2343 1657 1984 266 1994 414 2834 1170 1449 1321 2207 28 2289 176 533 347 2408 278 569 207 1940 1259 2227 1253 2586 1…
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: 1151 209 962 1006 368 376 403 1069 160 903 292 947 307 1098 646 1049 178 336 620 712 590 1128 93 365 297 389 55 1022 606 678 363 529 717 836 73 790 701 977 49 936 462 1027 9 810 255 1138 77 123 849 1102 99 697 696 768 78 721 414 585 191 311 414 450 578 1077 821 997 194 1024 244 329 478 597 546 626 861 1008 231 1065 758 879 520 557 122 497 290 610 321 894 533 1105 754 967 270 569 389 996 68 803 809 1079 368 987 197 1102 162 537 61 112 194 1016 61 866 550 635 51 556 816 1109 541 775 350 655 307 497 634 1063 134 650 991 1058 928 1003 445 801 17 276 54 449 157 741 180 468 290 1076 299 594 197 243 7 852 103 497 463 882 293 520 930 1145 785 1024 29 572 179 631 721 1047 983 992 516 1027 249 836 677 878 134 1010 219 371 186 729 921 1069 247 644 589 764 425 597 694 1047 220 1140 407 483 226 502 798…
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 <= 3826; 0 <= m <= 3826.

Loading...
Test Cases:No test cases
No test cases available.
The Verdant tunnels of Ivo - MEDIUM Coding Problem | CodeTikki