CT45762

The Ancient Build Order

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Caravans arrive at the observatory of Starfall with crates of roads, and Bhanu the customs officer 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 <= 1960; 0 <= m <= 1960.

Example 1:

Input: 1762 323 1506 1617 227 1080 485 1512 843 934 516 1521 1029 1689 485 802 275 1038 1474 1709 1177 1680 742 1647 643 1015 360 1619 234 489 97 1307 1144 1190 3 1597 93 164 65 1125 1391 1715 681 1652 149 391 916 1277 835 1590 1510 1689 1097 1099 52 111 1320 1388 18 1532 212 218 831 1752 262 1200 1342 1378 385 460 666 926 375 1718 34 269 530 658 4 1626 367 1112 919 1290 1106 1218 472 1461 3 1042 1371 1536 939 1332 1323 1634 860 1687 23 1593 130 811 383 1322 792 1545 461 1246 346 1542 942 1089 71 1740 542 618 56 644 416 1648 768 1646 584 1122 66 1439 1067 1244 613 1297 363 1453 256 329 409 927 486 604 1136 1238 234 649 1077 1543 233 743 603 788 672 1092 571 685 772 1314 1240 1596 225 1033 559 656 103 529 386 1100 291 999 223 719 194 482 117 771 1032 1367 49 809 421 1742 93 1373 376 1309 562 1595 …
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: 773 917 358 628 432 530 295 666 178 464 353 680 186 753 316 644 249 270 95 699 250 303 62 512 113 531 10 316 75 709 362 376 116 509 337 709 301 730 150 645 339 382 183 422 419 526 262 754 194 648 337 470 178 723 60 665 28 289 252 646 29 729 201 457 18 71 350 670 456 462 28 160 145 747 631 704 377 729 514 681 269 591 134 151 499 675 400 450 117 463 231 618 142 773 33 366 93 163 170 247 110 386 127 231 515 608 45 562 440 557 394 725 368 565 8 660 500 625 377 465 164 769 468 517 66 338 41 427 184 533 292 705 283 648 87 756 211 520 362 748 111 453 120 246 7 507 262 269 336 520 338 678 150 235 469 513 330 643 182 528 182 761 122 186 47 769 55 146 264 452 120 715 311 762 331 509 641 768 615 643 272 440 393 558 125 411 402 613 434 662 531 632 111 388 290 581 660 740 168 325 64 248 189 754 61 518 …
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: 1898 421 1539 1586 752 1104 117 1798 724 823 1019 1738 61 1221 1056 1514 670 843 17 469 201 1731 338 861 829 1638 1683 1816 987 1789 58 1743 109 285 85 1581 1163 1327 1182 1665 647 1005 577 659 690 1816 367 1229 355 1370 294 990 226 1592 523 869 225 880 1198 1718 414 1236 174 1690 1058 1341 478 1302 572 728 888 1524 408 981 336 986 244 831 374 1815 336 988 220 1787 1333 1881 252 479 1079 1130 1409 1723 775 1515 968 1501 598 622 971 1784 539 566 171 1547 738 1009 264 1207 40 815 1174 1218 441 1102 1091 1700 998 1174 1544 1793 423 1605 1321 1322 347 1753 1438 1880 1018 1716 866 1797 194 890 279 699 924 976 432 1837 1042 1645 207 1264 674 1256 46 1251 262 1678 576 1118 260 1522 1215 1767 150 952 27 1480 480 523 813 1290 482 830 835 1783 1594 1848 1328 1777 373 1234 52 1766 980 1879 9 1010 113…
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 <= 1960; 0 <= m <= 1960.

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