CT38744

The Build Order of Whitesnow

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

In the tundra station of Whitesnow, Peddler the quartermaster keeps careful count of the canals. Settle a dispute between crews, every figure matters. 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 <= 3403; 0 <= m <= 3403.

Example 1:

Input: 955 424 391 823 185 461 322 639 371 728 331 756 194 886 117 788 177 293 16 862 619 800 198 802 616 672 383 611 371 953 478 675 605 690 250 633 37 690 232 299 375 467 462 466 462 654 604 792 337 478 320 842 493 892 195 789 245 458 192 844 361 512 158 842 199 307 122 821 16 286 401 523 341 643 277 311 646 869 167 510 478 578 50 918 9 497 891 896 177 689 75 939 665 936 587 928 19 727 336 869 699 717 406 856 210 594 115 450 134 844 25 452 521 666 39 194 241 302 395 897 167 177 386 822 137 194 96 539 17 418 93 946 16 409 32 870 115 612 243 855 310 635 648 749 330 371 62 310 431 572 271 683 547 594 150 792 472 622 910 936 417 809 374 796 18 171 379 521 130 351 590 614 413 476 485 489 488 798 443 789 326 465 110 458 462 508 323 825 20 299 618 678 44 135 302 915 674 908 126 792 937 955 230 477 787…
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: 766 290 52 344 20 242 128 519 413 533 739 751 34 353 333 576 472 598 169 381 417 570 400 494 29 679 189 465 154 335 372 568 535 562 304 436 156 322 180 277 725 737 466 656 371 373 404 556 479 648 236 735 169 338 285 683 52 531 10 477 347 757 280 375 116 225 253 766 159 323 214 248 245 577 359 763 364 603 465 738 114 480 69 77 413 718 114 169 676 703 75 656 20 522 182 454 123 144 335 634 339 418 215 292 400 522 45 714 39 416 362 630 112 362 350 457 105 191 232 518 378 742 69 134 394 680 247 408 83 268 77 165 6 194 431 437 27 752 296 463 470 473 49 96 380 674 112 285 717 762 211 280 346 700 6 327 271 524 100 465 459 759 503 746 131 160 192 390 249 711 116 262 95 487 368 619 163 552 621 720 512 739 514 746 381 582 510 589 33 673 210 561 108 172 213 729 395 548 143 190 17 234 441 625 172 360 5…
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: 1778 658 1598 1670 512 785 638 1714 136 414 1 331 1226 1718 991 1482 406 1059 81 718 287 1138 197 892 1342 1532 741 1404 446 1384 1504 1676 809 1094 236 1418 493 1485 1201 1315 534 1034 645 1177 369 622 43 55 527 1518 443 1756 114 1638 605 1037 861 1557 749 971 940 1314 366 1642 803 1775 596 1602 129 917 414 1588 305 845 11 1009 394 1163 613 1263 435 1297 255 1276 158 1040 103 946 123 1697 617 800 379 1621 1156 1536 1395 1659 983 1266 1497 1585 803 1445 287 507 223 835 1011 1574 833 1200 23 200 306 1502 680 1476 979 1210 282 1465 326 1131 885 1291 175 610 53 1222 363 1192 130 1729 1004 1134 320 677 225 1247 232 1102 630 1261 731 1460 581 1163 248 1523 291 703 1169 1447 900 1571 243 1401 27 72 207 253 777 859 392 1298 637 1037 804 1526 1367 1728 797 1430 726 1720 706 975 19 1001 491 1202 38…
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 <= 3403; 0 <= m <= 3403.

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