CT49300

Cobbler's Ledger of canals

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Cobbler inherited the boathouse at the kelp forests of Tangledeep along with its curious bookkeeping system for canals. Time to make sense of it. 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 <= 2849; 0 <= m <= 2849.

Example 1:

Input: 1837 1442 199 822 1146 1622 915 981 551 917 1078 1095 956 975 393 692 1396 1771 675 1473 1068 1587 164 1458 310 1591 577 1362 1065 1621 71 1293 1220 1335 522 992 846 1721 545 1221 1540 1646 504 1536 706 1269 1081 1714 1116 1355 181 806 844 1574 29 1476 652 692 35 1542 123 368 199 1457 446 1831 882 1582 837 1517 402 440 247 1248 1201 1571 191 1753 99 1598 61 1384 629 1258 93 272 745 1762 470 1783 634 1487 190 725 69 1780 477 562 197 754 1654 1819 1350 1737 707 1509 1524 1688 911 1523 211 517 366 1452 289 1717 522 1174 253 1116 509 1277 1292 1401 304 598 520 1563 573 1677 977 1081 488 589 960 1284 267 437 1381 1835 1098 1305 224 384 1064 1481 1049 1572 786 792 827 902 425 1704 196 1458 842 1020 577 1015 90 322 697 1277 169 1147 422 676 560 1202 1707 1820 191 782 426 1108 228 1697 554 1761 45…
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: 1872 21 272 1245 526 661 805 1021 119 1522 63 155 835 1230 108 616 509 1495 1449 1598 642 1500 968 1850 453 1495 103 881 372 880 537 1099 1050 1330 460 1824 129 1322 627 811 1353 1562 65 1011
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: 2543 646 1279 2450 383 1831 1262 2058 1535 1867 1246 1335 2188 2407 47 2422 1349 2516 85 1798 901 1062 1816 2209 507 1339 603 2439 995 1364 177 2322 552 720 764 2430 1266 2287 151 2200 245 2543 1350 2106 2434 2540 189 1087 658 1654 1018 1407 156 2063 1343 2472 2083 2160 1332 2235 1960 2002 258 340 1023 1586 147 858 968 1889 744 1654 11 1905 1030 2151 1933 2520 1939 2052 898 1180 195 2020 268 1873 129 553 15 1283 113 1032 1975 2232 1287 2168 825 1622 785 2507 1501 1616 120 1908 1486 2284 1261 1874 829 2510 36 1514 2340 2531 550 665 2140 2412 462 1125 448 1107 1205 1854 1370 1841 393 2080 1294 1746 183 2537 317 893 974 2435 1110 1612 1870 2282 36 1659 910 1413 1050 1543 129 613 746 1144 1016 2386 1925 2475 386 2036 1020 1858 2134 2480 816 2191 147 1568 53 393 249 1078 1689 2002 862 942 1346 …
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 <= 2849; 0 <= m <= 2849.

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