CT54661

The Build Order Beneath Firewatch

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Xavi found an old ledger of canals in the mint attic at the caldera rim of Firewatch. The margin notes pose a precise question. 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 <= 2511; 0 <= m <= 2511.

Example 1:

Input: 1465 1021 152 1008 791 1009 81 968 598 1089 636 799 353 991 127 919 12 332 386 690 1040 1234 297 1242 77 881 15 1424 86 1207 403 991 743 979 929 973 217 623 262 1384 11 745 11 1024 1057 1073 311 863 29 1343 293 523 34 1428 953 1459 124 1208 421 558 760 1119 152 249 819 1241 1111 1244 1086 1274 807 1031 436 823 284 316 612 948 187 510 445 558 428 1251 44 443 137 773 323 582 34 904 8 855 240 266 223 251 464 1231 175 824 196 442 605 656 76 1337 623 895 840 1340 56 1326 559 1208 61 1284 29 884 475 1348 363 658 104 249 31 669 98 922 86 232 269 564 39 69 132 1260 451 836 441 916 529 891 686 1204 26 1029 478 1168 551 1168 106 581 389 507 209 1008 816 1353 709 1102 707 1159 810 949 498 1265 444 1112 600 668 55 1458 382 674 467 796 699 1405 889 1099 1094 1270 347 696 591 1025 367 1210 259 1356 70 1…
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: 1846 2300 89 542 740 1049 325 1528 290 1548 941 1276 591 1142 506 1093 483 1235 397 571 124 553 1090 1353 554 627 1396 1822 240 1394 1087 1120 646 1700 1205 1480 619 1491 532 1621 607 678 384 1197 1116 1505 153 1013 1576 1733 506 820 121 1774 767 1336 533 1134 781 1080 633 1280 1005 1105 1042 1110 24 26 369 1033 396 1347 1067 1731 551 906 1345 1503 646 1767 658 1697 863 1597 238 1787 1036 1392 1069 1281 772 838 358 805 975 1288 169 1573 1134 1513 199 206 815 1677 152 795 521 563 672 1804 463 937 465 665 588 807 487 1510 783 1455 157 1717 754 1220 40 1718 141 1357 75 1479 864 911 89 1303 954 1838 185 357 975 1244 357 1224 625 1581 300 1545 60 1440 1383 1480 576 1080 1519 1733 1569 1846 177 819 445 1298 251 771 642 916 910 1060 107 1812 168 519 1350 1796 1111 1819 304 1250 494 1039 236 1773 …
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: 1437 1019 76 993 362 1254 1245 1425 885 1361 324 501 718 1217 90 471 418 898 66 260 501 1168 1172 1293 780 1219 140 223 646 1322 654 1213 125 1116 169 1421 81 1264 639 948 1220 1255 173 1271 344 1116 286 547 323 1432 1145 1235 151 1174 161 803 1310 1399 736 785 1094 1375 1142 1259 5 1104 74 92 94 136 410 1079 816 1180 460 822 164 972 1096 1278 561 1210 128 589 282 1187 262 600 353 1098 786 1154 671 871 126 1347 517 807 69 537 230 543 389 1343 124 1058 426 570 48 1287 172 1165 100 1068 155 605 514 1153 553 1195 726 1339 356 574 384 1051 71 596 643 814 55 440 898 1176 399 990 1274 1359 913 1426 162 1419 447 652 789 889 417 1144 793 827 308 688 123 817 371 666 82 460 1176 1364 69 783 199 929 482 1016 882 1091 719 1191 794 899 247 897 858 1389 758 848 1122 1422 287 784 1121 1191 721 1294 175 1…
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 <= 2511; 0 <= m <= 2511.

Loading...
Test Cases:No test cases
No test cases available.
The Build Order Beneath Firewatch - MEDIUM Coding Problem | CodeTikki