CT60934

Shepherd's routes Build Order

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

At the floating docks of Skyharbor, Shepherd records each routes in a worn leather ledger. The guild wants answers, not guesses. 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 <= 2175; 0 <= m <= 2175.

Example 1:

Input: 2029 539 106 1531 235 1851 595 677 935 1034 808 1308 85 1339 1494 1878 719 931 278 1661 449 1569 1699 1776 1412 1831 352 838 1819 2012 97 1132 889 1041 145 1593 420 853 12 1905 570 765 883 1745 1236 1680 949 1620 868 1771 1246 1544 1132 1442 918 1901 1370 1866 53 1492 1399 1411 736 1303 180 1802 1948 2024 742 878 1795 1872 383 1665 396 1224 64 115 460 1299 1657 1947 720 1942 1835 1942 152 732 1553 1720 179 901 944 1937 448 1279 186 1047 1003 1460 903 1511 498 888 1739 1899 963 2027 302 1617 1523 1853 235 322 562 1214 757 848 1313 1534 576 1608 360 1047 1431 1699 579 1841 112 1362 885 1487 108 344 231 1620 198 1662 1291 1534 332 427 811 1471 547 845 321 1236 307 1558 889 1672 168 761 1328 1814 1190 1348 953 1695 1116 1872 63 1464 77 1689 1089 1863 21 768 947 1822 1246 1564 1462 1782 446 166…
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: 1729 1853 685 1560 684 1506 1142 1424 874 879 141 1591 346 692 773 1350 1011 1162 30 160 182 1339 1132 1165 702 850 96 561 117 1318 121 1093 63 1366 701 735 1103 1350 657 1490 1457 1477 240 1216 201 1343 1358 1436 623 1396 537 934 486 1705 50 1167 532 1385 280 795 216 295 234 662 1341 1598 437 796 212 920 3 314 573 1435 270 361 270 1210 97 1389 153 1209 206 1630 594 811 838 1179 26 792 999 1282 596 1274 632 926 96 1329 55 1039 8 252 436 1713 549 1176 223 449 157 983 886 1509 461 1608 845 1722 1255 1302 931 1517 14 1167 459 1659 199 1425 494 1637 957 1148 961 1663 760 800 532 1522 519 1039 532 974 520 1413 502 777 1101 1607 668 1714 90 1453 267 666 379 718 1277 1711 1116 1236 750 1457 734 1166 70 644 789 1340 260 504 1278 1655 841 1452 131 829 11 1322 5 338 661 1324 404 951 798 1176 211 140…
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: 331 1869 28 291 178 223 202 261 153 266 94 289 8 277 16 236 45 303 51 222 118 150 201 219 223 273 151 179 31 75 98 211 67 210 165 224 293 322 43 263 181 277 19 158 115 146 55 196 199 267 54 100 191 286 203 229 107 155 74 324 123 195 54 103 89 314 51 185 56 98 9 205 92 116 274 292 105 128 51 326 163 207 34 221 282 298 43 234 61 168 12 244 2 237 67 283 85 217 125 212 22 116 46 66 58 312 24 97 104 175 179 324 130 246 32 113 39 49 63 149 167 323 6 181 232 262 187 233 64 303 267 326 132 235 4 173 9 247 74 276 198 274 230 249 69 258 253 320 22 39 21 292 149 326 185 206 125 251 174 311 114 120 228 327 260 266 103 180 77 269 103 216 58 79 128 264 36 269 49 57 87 233 11 329 87 112 169 279 130 294 12 60 94 302 150 233 226 283 174 304 149 282 81 196 230 254 102 321 209 316 65 282 65 118 124 197 92 29…
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 <= 2175; 0 <= m <= 2175.

Loading...
Test Cases:No test cases
No test cases available.
Shepherd's routes Build Order - MEDIUM Coding Problem | CodeTikki