CT65344

The Build Order Beneath Mirrormere

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

The council of the lakeside town of Mirrormere pays by the answer, and Chaplain intends to earn it. First: the full register of bridges. 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 <= 2868; 0 <= m <= 2868.

Example 1:

Input: 2583 781 1227 2097 138 1173 943 1224 1032 2424 1599 2180 100 1418 530 1837 1953 1961 265 1408 856 1033 552 1315 72 1012 620 698 457 2138 600 1992 66 1797 138 1819 1391 2323 425 631 1591 2064 105 1530 233 1949 823 2119 1901 2213 1602 2008 975 1301 246 1692 1172 1919 1167 2422 1996 2126 80 1736 144 798 417 2025 688 2233 1318 2068 537 978 704 2290 2413 2555 714 1691 1787 1800 912 1818 304 1060 673 1671 26 2241 435 2016 243 1026 592 1167 987 2538 666 963 159 2527 1082 1949 1198 1365 74 1205 315 2213 271 1620 279 571 1356 2359 473 1495 419 2541 291 1277 192 217 2098 2441 315 2108 380 1396 519 1262 725 1380 1875 2413 1224 1746 215 1022 1040 2018 966 2284 88 1201 998 1315 632 1984 853 2126 1277 2581 814 1460 1186 2204 547 589 135 327 827 1479 114 1486 840 1983 126 513 970 1518 932 1482 450 2566 1…
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: 2014 2751 1597 2007 440 1654 1509 1852 981 1310 263 1433 1553 1627 85 1351 337 1355 289 522 907 1307 1690 1856 111 141 1045 1819 717 1197 690 1974 722 1220 239 1915 600 1653 301 1813 476 2004 10 1209 1012 1476 1063 1795 236 1229 44 1349 766 1695 749 1728 725 1603 791 1604 407 1012 312 318 616 1409 462 751 1019 1950 758 1231 1111 1564 1067 1253 1086 1746 266 1291 675 1883 763 1735 1208 1255 764 1323 792 1824 789 795 1352 1786 73 177 826 1507 537 1864 1274 1455 1102 1702 800 1417 124 713 441 1778 223 943 295 1426 674 1337 1723 1893 1557 1965 308 1073 1590 1969 1054 1143 713 1735 661 985 284 1781 35 76 1713 1874 581 2003 991 1882 1047 2007 83 411 654 1283 508 1173 212 1451 141 776 407 697 1748 1950 536 1435 1490 1881 1689 1695 595 621 282 753 77 1647 816 1793 1392 1435 1854 1993 976 1198 234 …
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: 1023 2481 631 689 178 298 322 579 518 871 37 70 965 985 313 602 103 538 150 497 60 178 15 168 45 581 208 558 84 854 305 688 770 967 202 361 171 935 638 755 300 558 208 607 421 748 616 833 23 435 584 709 275 790 813 871 427 936 378 1022 213 450 351 947 47 729 400 628 1006 1022 313 838 264 623 368 598 173 294 191 547 140 988 444 809 519 930 285 558 120 426 574 889 561 916 346 769 632 649 193 863 657 779 130 428 273 975 420 728 111 1014 59 248 300 999 516 801 223 406 714 897 375 976 242 789 505 626 231 839 923 954 241 593 648 1004 611 912 325 994 301 744 312 345 240 264 199 677 406 643 43 964 45 889 64 521 25 429 452 743 451 905 721 1015 311 914 365 612 181 744 136 146 154 622 387 765 709 730 516 940 251 440 634 654 515 935 170 234 128 291 588 973 97 629 135 779 213 519 914 949 517 663 592 79…
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 <= 2868; 0 <= m <= 2868.

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