CT63562

The corridors at Obsidian Shore

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Caravans arrive at the basalt cliffs of Obsidian Shore with crates of corridors, and Smith the bookkeeper 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 <= 933; 0 <= m <= 933.

Example 1:

Input: 722 578 168 310 113 406 181 353 582 702 112 514 434 695 18 418 237 610 107 519 467 508 125 587 52 156 588 630 62 278 461 516 215 654 232 419 103 499 89 436 363 434 654 678 655 672 96 333 181 709 455 561 58 416 364 482 369 651 165 559 454 559 317 358 410 603 27 546 562 605 199 226 399 482 393 451 223 325 88 547 170 617 103 551 132 506 362 522 23 465 441 457 369 487 79 239 142 369 22 189 477 501 305 540 43 184 713 716 91 120 57 620 65 207 118 155 518 671 59 542 305 571 24 283 247 456 126 677 68 445 468 480 104 439 176 386 273 501 28 521 116 182 156 253 278 420 572 602 429 606 290 514 217 224 181 642 419 562 327 558 533 572 199 249 238 559 220 435 641 647 47 157 335 677 46 659 66 592 101 307 393 429 31 596 147 695 26 411 367 386 263 295 121 204 28 318 294 449 410 501 86 115 13 587 100 410 340…
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: 26 325 21 25 9 19 3 13 3 11 8 20 7 26 17 25 2 24 6 8 3 7 3 9 20 23 1 23 4 25 8 23 12 17 11 16 15 16 7 20 1 3 16 17 4 6 1 2 9 20 16 24 10 24 8 11 8 17 13 20 1 8 24 26 5 8 16 26 4 23 2 17 23 24 1 12 22 24 20 24 11 25 3 4 5 7 2 5 1 4 1 7 19 24 15 17 11 21 16 19 14 25 12 20 4 7 12 25 16 21 3 5 1 13 10 23 20 21 7 22 2 21 11 23 4 21 8 21 8 18 8 22 1 21 6 16 10 17 1 15 21 26 15 19 1 17 7 14 1 5 2 19 2 22 2 23 9 23 4 22 7 17 2 15 13 15 2 12 3 19 20 25 18 24 1 25 8 9 9 26 9 21 6 11 12 18 1 6 2 6 22 25 1 9 12 22 8 24 5 9 6 7 10 22 19 21 1 14 5 6 18 23 6 22 10 19 14 17 14 19 6 21 6 12 14 24 4 14 11 15 22 23 6 24 7 25 12 26 10 16 14 20 14 22 11 20 13 25 2 10 13 14 20 22 1 18 6 13 15 21 5 11 6 19 15 23 12 24 1 22 11 18 12 16 5 26 3 18 8 10 3 20 9 18 5 15 5 13 4 8 18 25 15 22 19 25 23 25 6 15 16 23 12 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

Example 3:

Input: 471 232 229 452 456 469 252 366 93 210 277 331 109 388 41 438 211 406 9 132 288 325 382 460 287 424 155 198 125 232 205 371 258 373 387 467 312 435 8 295 7 95 161 284 151 383 87 202 43 192 196 268 144 253 91 163 183 378 76 199 26 279 401 409 52 381 24 197 245 356 105 350 19 241 176 394 11 460 19 91 127 327 145 229 87 418 324 414 144 363 220 433 122 151 356 417 92 378 100 299 90 349 190 223 126 271 401 434 94 451 42 434 314 387 39 54 57 357 9 150 21 330 280 400 340 382 5 133 67 85 85 413 62 466 285 447 68 265 257 416 426 446 63 123 14 427 252 271 170 437 62 422 46 216 196 373 44 107 197 440 157 336 226 285 86 153 293 457 114 317 19 368 194 227 4 468 48 69 348 435 70 83 138 390 60 78 203 411 227 341 183 451 255 328 102 165 377 424 9 304 7 169 343 469 215 304 19 130 211 412 206 469 99 104 312…
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 <= 933; 0 <= m <= 933.

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