CT49091

The Build Order of Bluehollow

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Qadir runs the loft at the indigo vats of Bluehollow. Today the books show a list of corridors, 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 <= 1916; 0 <= m <= 1916.

Example 1:

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

Example 2:

Input: 785 1781 639 662 40 274 218 591 266 353 201 512 49 655 374 687 64 466 279 650 350 606 277 784 642 746 91 302 502 509 94 324 220 482 563 743 417 662 66 284 71 601 128 438 358 713 222 760 106 390 1 9 411 598 315 478 481 764 213 645 302 649 568 618 69 690 110 115 437 443 339 396 95 538 119 701 471 510 485 528 449 685 427 684 197 568 459 781 298 509 177 783 148 184 535 724 261 380 564 701 252 491 38 385 589 597 325 353 552 758 176 390 320 618 121 728 438 729 251 721 254 437 370 382 193 347 20 543 420 668 605 641 133 556 381 738 37 78 447 625 452 653 496 697 426 784 134 482 315 698 308 692 618 640 376 658 55 187 75 347 50 277 39 590 108 232 51 129 300 305 442 472 407 657 253 446 630 728 23 182 419 711 368 704 253 394 91 708 236 299 209 552 353 373 319 509 400 434 422 523 570 571 127 453 534 668…
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: 822 1817 284 299 30 278 295 821 72 245 609 678 267 487 391 496 244 254 301 419 522 545 110 404 576 626 27 218 148 590 198 297 317 737 372 415 296 411 82 396 5 306 322 790 324 396 72 124 421 697 156 790 1 304 703 732 10 655 359 659 336 559 344 606 182 212 518 577 486 768 138 548 61 686 174 309 244 247 61 581 18 805 599 726 3 440 258 793 480 766 107 230 259 425 153 491 173 203 86 430 271 784 91 162 10 450 93 613 325 443 108 641 242 532 306 545 232 681 492 743 197 458 260 264 550 555 250 708 716 723 438 480 465 778 326 456 690 700 743 809 660 685 6 179 407 535 208 265 293 351 186 702 256 690 403 463 281 495 357 389 488 549 80 172 24 421 500 713 247 568 635 777 155 512 331 424 221 792 93 362 114 252 234 690 327 646 72 340 614 701 14 234 5 598 601 642 361 490 267 353 233 748 12 314 128 357 205 …
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 <= 1916; 0 <= m <= 1916.

Loading...
Test Cases:No test cases
No test cases available.
The Build Order of Bluehollow - MEDIUM Coding Problem | CodeTikki