CT62418

Zane's canals Reckoning

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Every season at the monsoon port of Rainhaven, someone must recover the missing manifest. This year the task falls to Zane, armed only with the canals 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 <= 2632; 0 <= m <= 2632.

Example 1:

Input: 1966 1535 301 754 901 1349 1506 1710 1522 1621 1627 1689 182 836 1343 1520 1148 1949 142 596 1700 1791 409 1241 1060 1226 338 1454 477 1485 42 1543 1365 1708 1282 1315 1057 1384 251 1549 135 196 1463 1601 95 644 1545 1653 686 1785 576 683 212 1586 567 1124 158 1097 264 1351 429 1113 1314 1880 275 1745 287 1640 897 1686 531 1877 426 532 324 943 1853 1892 153 865 814 1238 35 1399 1343 1534 376 664 1733 1747 822 1904 294 869 329 894 147 1375 192 1887 1473 1906 672 1241 443 1002 1599 1680 162 1278 514 1452 430 1928 1334 1741 1240 1368 864 1489 1408 1522 554 1878 340 1240 1025 1151 349 1835 1282 1775 94 1106 649 1355 756 1723 269 1173 534 692 603 1177 286 1002 1095 1334 797 1610 375 1132 160 1031 1280 1607 437 484 430 721 694 1608 419 981 316 965 220 911 206 292 795 1294 448 1527 165 317 522 15…
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: 1847 2151 967 1763 1223 1247 295 964 600 874 267 1111 1045 1279 872 1488 204 1011 662 1432 1030 1080 782 1414 235 1390 1086 1325 158 1611 346 1099 1287 1507 328 1737 557 1622 558 1684 528 1472 644 1129 64 1065 1278 1687 113 1819 665 1499 823 1546 1264 1688 803 1019 78 371 535 1636 1448 1832 1194 1445 189 1350 853 1135 652 1797 348 515 947 1286 944 1589 441 1662 303 1589 418 1321 935 1672 811 1120 1140 1765 1243 1618 258 1207 501 808 206 431 371 1564 242 1257 137 390 206 948 708 1833 679 843 491 1369 469 574 112 1511 660 1263 141 1322 180 1299 909 1476 1516 1572 257 808 23 297 1207 1621 205 1383 34 1444 1141 1374 608 1062 1042 1247 1408 1519 289 946 78 1790 840 920 1075 1325 349 1228 724 1686 965 1555 1518 1809 350 920 456 1759 1246 1741 22 209 137 1706 966 1819 30 1013 393 665 1713 1717 16…
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: 230 699 2 32 19 184 21 41 17 53 8 212 4 171 5 166 36 145 82 152 177 181 45 145 149 205 42 187 99 170 118 213 194 221 1 154 104 118 52 195 4 208 77 84 32 109 114 222 108 116 33 51 63 169 29 91 150 156 50 109 51 164 36 131 92 221 92 110 87 176 52 200 8 139 128 158 28 144 4 189 38 198 20 123 150 219 48 91 54 167 127 196 11 103 105 141 40 141 23 71 117 163 112 155 37 87 10 166 198 207 56 198 87 200 24 111 148 187 75 199 120 204 47 71 35 68 25 198 49 132 47 159 209 223 26 42 117 181 78 194 74 152 54 131 96 213 81 107 39 69 3 146 33 206 71 129 38 174 50 111 110 187 15 150 153 221 59 73 37 159 162 218 110 177 4 97 76 149 80 113 27 105 87 205 132 208 18 79 103 211 101 201 93 137 75 98 75 195 42 51 32 199 52 159 16 155 134 153 50 189 75 133 68 216 9 49 33 191 30 185 87 183 166 168 120 171 31 52 26 …
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 <= 2632; 0 <= m <= 2632.

Loading...
Test Cases:No test cases
No test cases available.
Zane's canals Reckoning - MEDIUM Coding Problem | CodeTikki