CT61539

The Build Order of Stonehallow

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Caravans arrive at the granite steps of Stonehallow with crates of tunnels, and Draper 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 <= 1287; 0 <= m <= 1287.

Example 1:

Input: 1015 692 757 900 345 719 108 938 84 863 419 501 144 186 565 676 180 415 423 611 401 706 487 562 660 1015 334 728 472 514 377 861 734 862 681 914 215 490 178 686 335 554 134 876 223 897 773 803 358 770 305 750 367 454 347 848 687 882 293 338 297 838 550 1004 78 428 226 706 795 871 730 867 56 116 217 480 418 957 339 395 136 596 656 743 90 762 933 959 554 596 550 945 114 351 109 605 407 641 322 698 133 891 187 950 216 502 304 378 86 301 408 692 167 545 566 772 102 248 11 289 314 632 523 938 364 688 898 1000 440 721 593 915 54 534 634 782 240 625 238 590 78 622 101 305 846 872 304 307 339 362 386 861 289 359 105 735 878 941 186 1005 508 959 200 273 426 557 587 720 479 735 199 865 111 896 255 408 2 139 859 1015 392 750 26 785 637 937 107 363 3 513 446 874 231 522 455 777 46 437 615 645 197 559 …
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: 648 1155 402 466 198 235 180 224 171 223 19 28 313 429 76 198 10 45 327 368 252 563 505 559 375 615 69 137 334 486 360 603 419 584 16 59 304 309 186 582 274 476 99 371 68 283 516 572 160 407 78 275 158 369 380 618 226 420 123 240 327 640 125 337 426 536 177 324 8 291 24 253 145 302 11 118 392 587 154 254 94 139 54 439 56 244 137 603 483 491 426 499 480 586 195 227 49 298 373 419 18 85 294 635 99 168 361 596 79 452 28 159 55 632 208 283 458 586 78 420 52 108 353 367 45 475 57 197 1 407 37 386 169 554 119 641 241 585 156 498 150 253 173 260 341 499 200 229 477 637 117 365 59 264 18 602 102 129 187 429 350 644 510 571 432 516 309 556 54 299 189 422 126 455 23 201 308 341 224 292 62 578 78 402 65 590 193 243 255 598 41 393 262 402 507 611 6 507 106 122 326 589 198 627 488 550 6 47 307 590 427 …
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: 859 678 160 668 723 824 368 764 19 87 2 775 373 782 61 712 129 576 741 812 243 513 764 852 582 735 596 792 165 826 150 354 148 482 493 696 342 738 153 607 601 679 291 503 227 702 156 244 448 496 406 598 609 789 109 576 484 748 660 854 396 414 56 325 341 368 157 416 106 337 245 619 79 344 431 491 573 758 44 351 103 703 306 525 170 781 232 548 38 336 140 284 67 395 242 727 773 789 152 285 147 476 330 410 192 724 5 63 292 652 316 625 58 632 186 230 28 408 230 683 107 250 137 408 441 816 305 606 226 499 384 749 372 376 287 453 539 738 168 859 90 716 83 550 49 699 79 111 394 630 606 676 555 629 296 479 251 786 196 563 75 777 133 780 252 562 656 850 704 754 122 551 194 364 546 596 570 836 266 628 62 844 110 204 691 818 9 121 137 666 644 794 346 790 450 760 581 620 585 597 472 764 308 546 50 445 …
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 <= 1287; 0 <= m <= 1287.

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