CT54918

Zane's Ledger of canals

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Zane runs the chandlery at the mountain city of Highreach. Today the books show a list of canals, and the numbers must be worked out before sundown. 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 <= 3752; 0 <= m <= 3752.

Example 1:

Input: 36 630 10 35 2 6 15 35 12 35 3 22 5 27 3 27 4 36 1 21 17 34 16 23 4 29 11 14 15 33 28 35 4 8 11 30 12 23 4 5 2 3 10 26 21 28 16 26 27 29 4 11 1 18 21 26 3 18 2 13 14 23 7 10 15 31 13 14 5 26 16 28 7 17 1 19 21 23 18 25 6 12 21 30 1 15 20 30 7 35 6 35 24 36 13 27 16 32 11 35 10 13 3 19 9 21 18 27 18 21 3 33 16 18 13 35 3 20 4 14 14 29 9 30 2 33 11 25 7 16 13 34 32 35 18 36 27 34 24 25 17 23 8 35 4 31 11 17 11 28 22 32 3 5 29 32 10 34 15 23 15 22 8 15 23 29 4 34 6 33 30 33 26 35 15 34 13 17 9 33 6 23 2 34 22 35 28 32 21 22 9 10 14 21 7 21 22 36 11 12 11 33 5 33 12 14 3 4 10 30 5 19 3 11 23 36 2 31 14 16 19 33 19 35 14 24 12 29 28 31 13 32 1 13 4 23 10 31 12 19 22 30 9 19 7 23 15 20 1 28 17 27 20 34 13 28 2 20 12 26 18 19 10 29 9 34 11 22 16 20 16 17 26 36 5 35 34 36 32 34 6 25 1 10 13 20 23 …
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

Example 2:

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

Example 3:

Input: 2432 3726 341 1624 1815 1937 318 1578 1812 2262 65 701 539 1095 1053 1264 1459 1731 1424 1537 850 1197 1177 1265 485 2214 1605 1759 1532 2224 135 1050 592 1329 1971 2051 716 1459 709 2295 250 2300 20 1851 1336 2274 405 2325 1094 1881 2026 2273 1998 2154 671 826 1065 2414 537 2353 995 2190 1211 2424 656 1338 61 2417 392 2202 715 1559 1195 2389 45 2047 474 1124 1523 2189 194 542 324 659 433 673 2048 2298 1069 2196 1157 2426 1590 1603 220 1420 1319 1915 2062 2073 628 1754 1831 1956 1606 2325 675 1894 1158 1831 771 1706 1132 2000 246 1463 1113 1687 1368 1677 2088 2313 1002 1495 1402 2390 739 1010 163 405 1076 1355 1003 1355 1214 1741 669 1478 57 2197 1195 1944 509 1390 235 962 23 290 462 578 344 2414 15 702 190 1919 1400 1605 1301 1604 967 1849 697 1459 1128 1937 284 1192 1145 1761 350 1641 34…
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 <= 3752; 0 <= m <= 3752.

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