CT63464

The corridors Build Order Puzzle

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Morning light hits the quays of Driftwood as Miller unrolls the day's manifest of corridors. The tally will decide the next shipment. 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 <= 2474; 0 <= m <= 2474.

Example 1:

Input: 2400 1793 1463 1913 1289 2145 1428 1728 154 807 224 1305 524 804 967 1605 1997 2312 1950 2140 387 563 378 1432 1616 1784 672 1469 82 1434 1443 1666 1349 2052 741 1583 59 1262 1091 1321 1598 2267 1317 1587 52 1682 1234 1346 1083 1487 1392 1564 50 1568 1616 2077 1175 1835 327 719 422 593 1419 2015 264 2157 1491 1957 1070 1652 1875 2040 1457 2046 141 725 296 2199 1530 1644 1271 2236 907 1732 1104 1794 547 2332 1258 2094 1273 1971 96 1869 263 939 1368 1507 816 1963 602 704 324 1565 1076 2324 142 935 1007 1427 389 1703 627 2045 1420 1624 1274 1537 717 2138 456 2005 164 2049 910 1605 497 1918 1439 2025 1121 1812 1795 2016 101 713 904 1899 111 2393 1670 2012 2105 2335 2002 2298 1526 2063 17 1522 1170 1894 1369 1717 85 1780 21 1820 598 924 1187 1536 265 498 749 1583 510 575 1659 2066 220 441 589 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: 2045 938 19 814 172 536 696 1066 1517 1832 288 1318 20 1249 1080 1737 728 1542 1365 1519 1866 1960 53 1265 190 1144 230 1527 504 1098 10 796 318 482 1061 1956 1541 1571 1400 1573 373 1651 196 1032 6 668 1372 1647 1244 1593 229 1683 1164 1805 176 207 1148 1797 702 1296 1822 1973 809 1565 325 1268 267 562 674 1628 1080 1113 1156 2043 344 1678 651 1128 1072 1442 1360 1568 732 1844 663 1912 777 1165 1052 1986 495 1617 1690 1820 218 1610 174 1571 155 971 242 1146 219 358 1565 1920 547 1763 693 1690 239 1940 1125 1338 497 1795 410 732 336 401 589 761 1452 1871 998 1664 516 1696 59 1352 1166 1338 944 1321 95 1368 542 813 655 1927 55 1905 472 1648 1294 1596 26 956 86 950 1393 1642 415 1900 100 1071 347 1267 818 1038 1123 1452 1580 1994 357 1673 201 334 113 157 79 1498 93 957 521 1118 805 897 547 8…
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: 1808 1700 451 1099 640 1608 172 1429 130 407 784 1036 150 216 350 1136 931 1319 111 1460 1231 1617 1160 1387 58 1039 681 905 247 1406 828 902 288 1231 1202 1328 184 649 29 246 362 642 88 686 185 1367 201 929 1532 1666 600 1482 1391 1582 457 1415 486 988 156 334 115 1503 585 1355 336 820 392 1394 708 1531 1548 1770 694 1088 626 1154 1171 1526 619 622 703 1361 190 469 836 1651 834 1622 1258 1356 979 1392 955 976 1302 1379 229 1485 105 599 241 901 575 1588 876 1788 1489 1657 1037 1447 85 1653 1767 1790 162 990 280 1616 1186 1630 362 432 763 894 1522 1735 1057 1452 482 977 66 886 1277 1315 719 1033 314 1000 436 870 1230 1782 33 1078 293 1046 439 1430 1332 1568 1357 1629 146 1312 732 1026 1282 1485 408 1537 620 1592 1142 1404 1278 1713 966 1161 499 1565 932 1499 12 1326 247 1375 255 1043 8 1290…
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 <= 2474; 0 <= m <= 2474.

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