CT61374

Shimmering bridges Build Order

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

At the ivory gates of Alabast, Tracker records each bridges in a worn leather ledger. The guild wants answers, not guesses. 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 <= 2801; 0 <= m <= 2801.

Example 1:

Input: 1551 739 223 247 180 698 218 318 228 1188 129 383 27 330 446 1130 384 966 715 1111 132 469 813 1203 938 1205 301 991 1398 1539 57 1198 137 1477 482 1225 533 589 125 473 266 1046 417 794 608 647 682 950 581 658 43 359 540 1360 794 918 1029 1443 1318 1474 249 1101 817 1146 629 1061 406 705 114 824 126 964 354 1434 48 1362 912 1406 693 1220 629 1030 282 1018 286 696 808 1206 295 1280 921 1294 571 622 1046 1055 965 1494 176 1077 512 1136 895 962 472 1348 225 1065 1237 1495 98 609 662 870 325 564 464 962 756 819 192 830 56 1115 349 999 691 808 727 1367 655 1245 1193 1407 1372 1442 454 1243 409 1327 486 1131 931 1298 711 939 467 1125 151 1536 599 1234 370 823 1007 1227 398 696 481 756 910 1209 507 1219 221 1544 14 1201 141 634 1050 1460 17 134 585 831 927 1283 512 737 383 738 160 508 1181 1276 2…
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: 2450 1306 1746 1891 675 2165 720 744 600 1858 1564 1875 1571 2121 396 1352 1203 1755 166 474 562 1776 789 1785 1595 2195 645 1681 2122 2434 892 1066 1787 1944 281 916 965 1293 1642 2004 444 575 1570 1685 1655 2047 232 2027 745 873 1071 1828 291 1262 1332 1436 1095 1465 1567 1691 197 1723 1409 1500 229 2405 555 1477 2 2191 980 1682 287 473 1549 1834 2166 2179 528 673 864 1734 1301 1932 193 205 1440 1975 386 1894 900 2050 385 2396 42 2306 375 635 648 1389 1263 2441 5 1731 643 668 981 1493 2154 2436 1479 1529 1344 1928 532 1366 1273 1480 310 928 750 1117 1087 1673 1071 2196 725 750 100 458 157 252 638 880 264 2021 638 1681 56 675 356 2199 802 1860 1169 1524 653 2163 566 1180 21 1743 1028 1333 1956 1968 95 106 148 2277 932 2360 803 1351 1485 2443 109 2130 1247 2147 447 2176 1755 1909 199 1201 …
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: 1994 1041 689 1932 421 497 616 833 891 1054 246 567 791 939 1560 1644 399 1487 1065 1651 114 1513 203 516 709 1878 382 1087 1267 1744 1188 1353 91 1418 125 637 854 898 890 1672 216 1434 414 1255 1371 1845 367 879 1483 1977 788 797 185 1846 181 353 1290 1535 908 1929 1009 1446 1350 1626 481 1172 675 984 447 1586 1260 1299 378 739 1098 1773 413 732 801 1288 933 1513 1136 1656 111 408 833 1893 1530 1979 519 1412 777 1031 140 191 654 1365 623 917 129 934 1515 1783 277 1469 573 1404 268 1409 264 1262 1728 1919 92 561 1258 1872 126 1176 1052 1193 997 1191 50 1889 636 1781 119 530 148 739 426 1667 440 535 68 1550 537 1069 601 1526 163 1684 704 1417 114 604 1025 1943 419 1784 305 680 715 1635 929 1139 281 1037 1110 1358 1069 1960 454 712 931 1067 655 1791 217 289 748 1527 1103 1804 1864 1984 1047 …
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 <= 2801; 0 <= m <= 2801.

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