CT54853

The corridors at Ashfall

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Caravans arrive at the ember dunes of Ashfall with crates of corridors, and Piper the accountant must account for every last one. 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 <= 3513; 0 <= m <= 3513.

Example 1:

Input: 413 2714 137 387 80 373 23 389 23 304 45 161 69 283 16 170 26 155 64 408 224 402 51 341 68 172 300 339 59 336 142 412 368 406 72 154 137 285 90 164 117 348 154 374 208 347 65 288 180 224 302 397 73 125 81 362 264 368 31 377 284 390 105 226 83 273 234 291 206 390 76 85 374 404 140 380 210 287 130 256 17 216 43 365 115 370 132 386 344 398 184 301 54 211 223 328 11 114 79 334 198 215 71 243 167 200 15 370 58 318 352 389 198 317 79 322 234 317 177 359 367 413 34 275 224 407 19 206 129 265 263 381 14 28 48 217 6 345 216 382 30 386 55 172 98 402 169 348 3 281 326 385 147 398 20 333 81 164 194 329 297 340 115 143 12 119 139 328 78 255 326 384 7 277 124 149 18 365 243 385 289 347 163 190 48 134 9 365 189 319 22 190 92 203 91 409 218 386 138 250 97 210 83 408 162 308 54 195 34 88 190 237 142 161 22…
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: 2963 2340 597 671 858 1419 758 917 1605 2567 2253 2919 2069 2532 1353 2767 138 443 227 732 311 1316 874 1850 677 2245 255 1843 393 2875 264 2876 1769 2456 132 177 560 2205 1357 2568 338 2934 218 2266 1404 1554 1331 1668 1843 2277 2365 2642 636 1498 738 886 189 2414 1908 2062 808 1972 978 1315 577 1192 2160 2852 1172 2451 561 1604 1152 1289 1060 2455 906 2338 1626 2803 1372 1753 1589 2046 1068 1429 442 1798 386 2557 1519 2510 1843 2102 1264 2119 1424 1520 1081 2607 1135 2079 2580 2854 564 2326 2600 2905 950 1519 1885 1990 540 1580 2270 2331 1027 2371 1681 2131 655 2625 843 1568 1635 2314 1349 1673 983 1633 1129 1139 368 2211 1462 2450 1693 2545 260 1616 1270 2129 521 2340 1893 2345 708 2095 229 2533 1433 2669 1422 2421 1647 1826 1078 1477 1540 2060 519 1246 2709 2735 1755 2570 1093 1871 543…
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: 217 2129 36 106 49 137 14 52 88 118 110 187 79 188 114 198 202 211 130 181 103 133 156 212 102 181 14 46 157 173 92 216 80 124 180 189 102 161 158 172 4 208 57 62 76 152 40 153 195 211 74 109 14 173 60 196 118 194 131 203 20 173 106 187 139 160 17 182 43 156 11 33 42 101 36 184 90 135 8 215 15 117 32 176 196 204 122 144 30 33 24 130 147 166 134 176 71 97 100 112 73 119 47 114 6 162 107 215 146 163 7 87 66 209 16 19 20 168 103 136 42 123 124 130 70 182 81 122 64 158 88 162 150 194 80 165 58 147 101 142 96 104 110 178 45 191 13 49 99 212 75 100 157 204 12 202 86 187 113 212 120 132 6 104 1 114 7 110 62 112 148 159 87 188 26 131 89 183 151 178 66 166 177 210 87 138 148 165 121 171 27 155 119 173 88 209 18 98 62 66 109 197 33 165 13 121 53 168 53 196 150 202 74 137 6 178 41 112 7 73 3 210 66 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

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The corridors at Ashfall - MEDIUM Coding Problem | CodeTikki