CT40358

Cobbler's Build Order Ledger

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Cobbler the tallyman watches over the gristmill of Rye Hollow's stores of bridges. A careful computation stands between order and chaos. 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 <= 2978; 0 <= m <= 2978.

Example 1:

Input: 2432 1425 435 2025 1736 1972 435 994 73 259 1272 1504 373 385 748 1321 150 1353 1303 2107 1217 1457 273 1777 2006 2178 1119 1742 1077 2033 621 1103 1205 1673 556 2129 689 1889 294 1403 1106 1732 2095 2157 1257 1555 550 1197 1588 2175 1373 1579 1080 1704 1272 1896 295 1625 1620 1996 513 1297 562 1587 1599 2047 1539 2420 625 1789 462 1785 273 1823 603 2001 392 601 146 335 370 1302 1305 1682 1531 1760 1052 2309 158 1570 1527 1671 463 2008 124 682 196 1335 110 2036 1605 1933 1849 2020 827 1485 1155 1912 1584 1659 1771 2396 1404 1577 711 1323 207 1769 1825 2047 22 714 159 1646 47 1130 2059 2109 999 2113 102 797 665 1903 2007 2239 482 613 1273 1435 9 341 255 1866 68 311 79 674 74 1899 1095 2427 212 1631 546 2403 884 2413 645 1621 1472 2056 2076 2243 1359 1398 1407 1925 552 1867 546 1876 1118 197…
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: 1311 365 368 1203 709 1049 453 1171 946 1307 465 942 565 683 638 999 1092 1149 411 1158 1126 1207 154 292 639 1063 579 658 199 289 157 711 100 920 727 923 160 716 664 1007 688 1125 378 491 333 950 484 647 54 1260 429 829 184 457 849 1139 270 545 318 1262 812 944 337 919 689 1053 76 741 298 489 652 1100 310 879 639 919 317 1046 355 1289 753 1286 112 350 230 1070 90 259 547 586 352 1049 760 835 92 975 697 855 363 1141 34 924 738 1227 16 1048 1142 1204 407 811 223 1147 691 710 80 602 169 619 254 1295 44 909 215 866 75 189 195 806 500 825 296 975 1202 1239 404 651 982 1057 26 674 348 842 871 1284 355 1019 70 979 248 724 104 117 287 579 84 976 151 212 917 1287 1062 1172 282 880 219 338 455 668 565 725 724 899 177 365 269 1272 112 1303 267 475 958 978 401 804 666 679 228 1005 645 817 640 1239 20…
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: 2948 1541 83 1802 199 2904 598 1595 783 1110 113 1664 509 2541 1925 2611 239 2894 807 818 2146 2524 1555 2736 1557 2359 1902 2347 1081 1451 450 601 2451 2861 1478 2340 1868 2639 396 1929 364 1153 1 379 112 2933 994 1187 1531 1587 842 1704 672 1910 31 1217 914 2435 501 1027 1169 2851 866 1140 1801 2871 657 2031 1040 1996 101 1960 810 1517 654 985 255 1446 2392 2511 723 2509 3 2399 2660 2791 1206 2760 338 655 896 2120 701 734 1800 2436 1646 2615 2264 2355 1999 2626 1873 2132 723 2483 1000 2138 1397 2556 394 2063 926 1066 520 1434 1936 2927 1650 2157 1432 2782 1063 2742 448 1260 2297 2310 898 1368 886 2689 147 2320 84 1650 936 1522 212 1048 632 2077 365 2499 596 1074 2385 2474 229 1120 1414 2587 1784 2506 34 1205 184 1634 110 1004 320 871 574 678 515 2026 531 2591 820 1144 139 2459 153 2751 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 …

Constraints:

1 <= n <= 2978; 0 <= m <= 2978.

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