CT36343

The Hidden canals of Trader

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Trader found an old ledger of canals in the timber yard attic at the floating docks of Skyharbor. 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 <= 1352; 0 <= m <= 1352.

Example 1:

Input: 374 115 44 368 81 289 174 271 49 97 16 279 18 126 111 309 267 293 3 362 184 259 321 367 51 284 34 225 15 74 12 75 143 205 240 326 156 172 187 211 311 352 86 353 148 355 18 245 236 300 205 228 46 91 77 359 166 328 162 372 187 210 48 145 83 118 156 197 256 270 98 349 82 344 210 282 72 313 181 199 151 171 123 173 138 202 219 353 97 256 67 152 93 109 94 191 209 304 39 129 279 299 80 249 234 322 307 309 154 294 78 247 122 364 118 285 21 247 92 339 28 357 218 369 48 126 72 123 210 317 14 100 14 126 89 191 12 295 176 311 138 319 122 215 25 315 85 318 75 274 98 136 148 258 106 172 14 63 283 317 67 91 285 316 79 208 129 272 69 336 97 122 114 141 151 265 189 226 6 46 16 39 27 81 120 167 157 162 77 314 85 226 306 341 235 296 33 360 130 153 89 263 197 321 122 220 132 311 294 312 3 30 56 166 186 297 13…
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: 661 315 548 653 25 105 152 526 335 371 3 142 276 526 399 420 475 487 239 574 33 71 85 234 22 338 401 539 293 304 142 200 154 408 303 450 27 222 87 615 144 316 476 552 216 598 413 534 107 240 222 494 430 441 31 65 31 548 233 327 220 537 58 403 289 330 294 325 222 571 69 244 147 222 152 202 88 257 233 264 94 487 55 619 388 453 36 408 288 514 347 549 237 346 396 475 469 645 182 517 465 487 123 363 8 60 131 482 385 403 104 568 188 411 171 646 331 359 226 591 226 341 556 649 26 411 116 448 137 270 123 453 362 638 333 651 276 513 155 341 333 595 206 256 387 548 162 562 128 155 234 606 19 203 191 385 315 591 256 399 238 413 80 243 395 524 345 547 484 582 534 566 175 218 530 600 360 582 277 337 19 164 382 579 222 508 168 379 72 338 319 506 380 492 560 624 488 644 199 479 133 277 308 476 449 524 18…
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: 43 141 10 33 2 13 23 36 9 34 2 17 4 24 21 28 9 38 25 31 22 43 22 36 30 39 16 36 15 23 21 35 6 28 14 31 32 37 3 36 1 14 15 31 18 33 8 21 28 37 8 16 8 15 2 41 25 40 32 40 6 30 22 33 30 36 4 25 8 39 12 14 8 22 25 26 16 29 1 16 13 33 14 36 21 33 2 12 21 30 13 29 35 36 1 6 6 17 3 35 10 36 13 18 12 25 18 36 29 40 13 30 2 31 8 12 7 13 19 43 17 43 15 27 6 43 3 23 24 42 16 38 33 39 27 34 16 42 16 19 26 32 21 42 11 23 5 31 1 8 22 32 28 30 27 42 29 42 1 29 33 34 17 25 13 39 13 28 38 41 3 17 7 39 10 17 6 33 9 19 1 33 22 41 15 39 22 27 19 20 15 41 8 14 14 40 24 40 25 38 12 30 2 27 21 31 34 36 3 18 4 31 10 41 9 16 32 33 6 16 30 38 10 18 27 43 18 32 1 21 12 16 9 28 23 39 12 27 28 39 6 14 7 28 24 29 7 31 2 15 9 24 3 21 31 43 18 39 32 43 14 23 10 21 17 26 3 33 1 24 36 40 16 23 1 30 7 30 23 33 15 40 27 29
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

Constraints:

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

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