CT63986

Captain and the Mossy routes

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Morning light hits the ember dunes of Ashfall as Captain unrolls the day's manifest of routes. The tally will decide the next shipment. 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 <= 1970; 0 <= m <= 1970.

Example 1:

Input: 1236 1396 968 1168 73 118 504 625 375 1201 221 1067 780 869 350 1067 398 911 67 73 168 1148 24 884 478 771 347 397 210 509 201 888 558 1139 14 942 805 1132 158 1127 236 1039 669 741 958 1072 651 901 674 897 588 925 947 952 488 903 401 753 738 1189 53 1083 156 823 353 778 26 850 840 904 402 1013 881 1015 262 750 371 1117 627 1016 544 623 375 1135 496 948 571 1179 838 976 155 993 249 1074 451 1225 95 324 443 552 216 349 507 636 607 874 575 919 148 317 520 560 104 1151 1133 1176 174 713 344 372 827 1216 613 1039 121 223 339 640 411 1060 611 1039 453 1038 26 452 31 1116 772 1041 148 538 193 511 650 738 311 849 294 1134 112 545 672 691 269 1179 25 504 861 872 521 698 297 704 459 1047 142 309 970 1076 172 796 148 1223 24 309 948 968 341 443 679 1064 969 1184 580 849 65 1212 830 1233 405 1119 904…
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: 1460 736 242 736 258 1176 1075 1438 710 1056 543 1432 176 620 946 1377 654 1188 1319 1333 59 1441 100 1435 149 491 1050 1180 913 1369 582 966 1233 1356 848 1244 690 1390 702 1132 267 1053 678 932 846 1000 184 925 117 1236 443 1192 133 510 614 1343 443 516 902 1194 654 747 1150 1234 518 1050 1197 1351 232 285 889 912 155 401 463 955 16 257 159 440 212 1160 54 771 785 1311 907 1199 108 164 22 386 228 771 679 1350 1073 1274 16 677 1136 1347 446 1398 655 831 472 654 157 1271 962 1175 585 1292 151 531 300 1386 471 1196 640 1309 771 1293 819 951 880 1420 474 1312 470 853 417 1009 320 564 317 1310 86 178 347 480 920 1047 240 891 60 148 702 1228 1042 1232 602 777 418 1058 130 484 89 1074 85 941 307 371 407 1387 39 1276 937 1165 1 1305 1153 1353 11 1295 995 1328 79 1025 206 1438 558 859 959 1125 72…
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: 1965 816 551 669 463 1458 260 1531 549 1706 372 1022 485 1578 305 503 5 382 435 1153 1180 1491 164 479 1003 1138 1144 1893 531 869 152 1291 287 1711 132 315 648 848 79 1235 622 1534 865 1903 469 1647 648 1633 1508 1859 799 1803 488 1127 66 1807 226 1287 425 1480 562 1532 687 1606 467 635 833 910 318 1452 1063 1200 1653 1895 71 1622 812 944 410 848 35 1865 458 985 263 1652 122 1624 1029 1530 309 849 385 1096 991 1439 162 534 772 1074 633 912 613 1348 267 536 1085 1592 1082 1858 1371 1387 43 116 76 384 178 184 123 360 331 1372 1578 1700 414 859 1096 1591 474 1741 755 1429 639 1854 1357 1798 722 915 1234 1340 1553 1641 813 1871 170 661 1429 1554 701 1252 552 1954 511 1007 140 411 23 514 1508 1821 1471 1945 133 1548 74 1747 551 1653 1651 1906 1648 1818 899 1035 117 1141 1194 1823 869 1954 516 …
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 <= 1970; 0 <= m <= 1970.

Loading...
Test Cases:No test cases
No test cases available.
Captain and the Mossy routes - MEDIUM Coding Problem | CodeTikki