CT37561

Cobbler and the Build Order

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Every season at the mountain city of Highreach, someone must approve the repair estimates. This year the task falls to Cobbler, armed only with the tunnels register. 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 <= 3025; 0 <= m <= 3025.

Example 1:

Input: 1834 2673 1124 1783 330 1369 181 671 924 1323 275 320 372 1090 343 714 1018 1554 385 510 1382 1823 25 155 668 1096 199 1651 1249 1485 34 1429 105 1281 953 1129 1410 1715 581 1481 1391 1819 427 1607 747 1338 238 912 416 686 587 955 72 685 227 1103 902 1237 665 719 132 1164 353 1053 709 1195 638 1462 1452 1596 1291 1517 345 1816 687 1081 691 1315 375 1295 1544 1597 196 1101 692 1079 762 1517 652 695 151 1207 523 633 570 1759 1328 1783 282 880 334 1518 865 1608 982 1091 986 1455 360 1661 213 1331 1095 1107 554 1786 236 1552 339 1423 417 1646 306 1641 574 900 4 678 72 1064 1476 1535 605 1662 524 1527 176 1819 86 1049 1243 1427 820 1413 425 1298 1132 1389 759 1337 993 1026 997 1459 607 1720 108 1579 365 1563 513 1244 202 906 36 1234 1256 1666 198 1800 180 1253 311 738 34 510 1286 1512 210 691 5…
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: 2933 726 1292 2098 782 1491 327 1976 2337 2904 1778 1919 732 1244 1470 1553 1743 2542 473 2168 727 2338 2144 2933 2087 2299 969 2418 1386 1593 285 2395 1288 2927 2709 2813 417 2712 669 1211 687 1459 408 1680 1360 1423 1328 1705 648 1804 287 982 1516 2052 378 1601 1919 2263 1172 2851 210 2571 621 1464 456 2341 1126 2781 2114 2503 541 2724 1303 1722 1744 2426 2674 2816 1125 1184 1167 1195 2656 2677 217 1595 300 1080 1226 2386 222 494 524 1444 1625 2596 1326 1501 4 1826 708 1310 1514 1907 618 2433 895 2131 652 916 190 2274 2216 2631 1388 2607 1711 2567 1757 2117 2750 2911 272 2257 132 2592 98 2629 1142 1619 1258 1293 1795 2835 1177 1602 660 1164 2359 2709 302 525 2501 2860 1238 1699 658 1554 2069 2458 87 1721 1248 1653 206 1096 2403 2700 1388 2379 1557 1912 807 2813 2281 2369 380 509 1008 267…
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: 2825 250 13 663 176 993 1124 1612 980 1643 76 2788 2370 2551 868 946 683 2212 84 324 2135 2454 2237 2496 1557 1693 329 429 2615 2663 2516 2681 476 2642 263 376 612 1964 544 1503 1496 2757 333 1483 1985 2751 1534 2527 337 402 1727 2742 1571 2274 1298 2624 1149 2340 1282 2793 215 756 139 681 1712 2046 2026 2212 208 347 656 1226 866 1164 823 896 1694 1947 2479 2794 306 1518 71 963 2434 2461 525 2026 603 1228 100 2805 851 2604 1975 2210 897 1926 1407 2639 1226 2460 1414 2106 1723 2210 847 1000 1470 2107 505 2449 1411 2111 152 254 198 1472 323 469 1460 2196 1268 2289 159 1668 1592 2600 106 774 24 828 1011 1412 856 1618 1898 1912 670 1497 384 594 373 1764 846 2049 442 1648 1721 1966 1781 2565 556 1139 2564 2637 248 1898 1601 1749 622 846 1138 2471 283 1707 1248 1913 354 1146 2353 2364 1605 1720 …
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 <= 3025; 0 <= m <= 3025.

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