CT63127

The Build Order Beneath Saprun

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Caravans arrive at the maple sugarbush of Saprun with crates of canals, and Bhavi the quartermaster 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 <= 970; 0 <= m <= 970.

Example 1:

Input: 824 261 684 753 90 455 383 758 134 775 314 427 404 617 31 765 18 370 421 699 317 661 264 744 441 792 43 462 172 274 82 268 12 801 150 591 123 655 532 816 8 735 411 590 461 554 754 786 210 737 145 419 144 759 99 774 95 682 137 549 402 744 231 232 506 611 138 315 12 750 126 822 685 805 230 574 572 605 159 246 136 400 468 595 61 756 206 716 661 686 300 698 672 797 162 509 317 432 106 636 281 310 528 615 385 796 428 582 586 699 107 141 415 690 312 316 204 576 535 589 341 531 80 326 285 450 382 821 209 624 452 789 351 500 347 549 199 760 457 544 27 250 227 611 62 380 416 452 271 345 147 329 42 704 144 631 119 241 250 320 117 576 58 536 107 480 323 723 64 357 167 257 194 266 155 774 139 741 273 776 307 418 80 465 12 373 189 655 724 797 315 689 38 466 3 206 95 520 333 773 192 439 224 551 224 470 …
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: 62 316 1 54 27 28 30 39 20 37 27 37 16 21 7 38 1 39 8 50 40 59 20 39 14 60 22 56 32 55 20 41 4 28 5 51 23 54 33 55 17 26 37 44 11 35 16 57 19 33 20 30 4 7 47 53 1 41 32 47 22 58 18 61 3 62 15 28 19 37 58 60 21 58 29 39 2 43 27 47 49 59 9 29 1 60 35 43 39 45 35 50 10 21 16 27 22 31 46 56 4 20 5 61 27 31 33 49 7 30 47 50 27 32 6 55 39 58 17 47 52 55 9 52 54 61 13 30 52 54 33 60 22 24 3 50 46 62 7 8 3 46 28 35 2 27 3 12 1 52 23 32 38 59 4 18 12 19 18 49 34 61 16 28 25 49 23 24 6 41 6 26 54 57 26 33 12 14 17 36 38 53 18 56 38 54 18 45 13 47 22 53 2 60 24 45 38 41 3 34 27 57 3 24 4 36 2 8 34 57 43 49 16 41 27 30 5 8 27 34 7 26 43 45 9 54 4 56 10 45 19 28 54 59 19 48 3 6 28 36 33 39 15 30 5 12 16 43 12 47 25 37 5 55 1 14 17 28 14 54 1 59 13 55 2 28 17 25 13 46 16 33 5 47 24 53 19 55 15 62 32 49 …
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

Example 3:

Input: 837 360 306 624 271 531 161 663 370 594 481 832 1 393 2 92 285 836 180 350 90 399 174 231 10 827 37 610 34 182 158 643 286 474 126 623 303 738 496 638 598 746 162 546 43 691 367 538 246 770 83 271 110 582 24 25 333 501 72 190 116 776 415 772 3 521 523 686 406 616 422 834 578 591 110 752 280 566 89 181 579 634 101 455 153 358 5 522 416 741 50 202 210 612 306 345 106 502 8 291 717 732 163 466 307 425 92 418 583 591 51 783 56 762 114 590 16 556 198 694 636 706 434 463 293 524 75 137 245 442 290 785 77 473 20 222 360 385 75 503 99 765 330 752 539 581 126 542 567 660 176 430 272 407 481 822 94 734 105 620 192 714 209 466 200 294 348 364 365 732 223 596 256 260 290 331 31 819 568 804 68 433 248 485 8 231 117 644 414 683 87 624 408 650 44 212 166 584 157 492 130 546 562 714 677 750 247 636 55 533…
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 <= 970; 0 <= m <= 970.

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