CT45872

Ashen roads Build Order

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Before the gates of the lily shoals of Padmore close for winter, Nyssa must finish the roads ledger - one figure at a time. 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 <= 3056; 0 <= m <= 3056.

Example 1:

Input: 1603 1950 1172 1214 200 997 1126 1372 356 1580 1067 1141 1037 1351 198 327 411 1470 182 205 308 485 110 1067 101 1247 98 856 734 1523 650 1493 568 1460 160 1466 270 811 493 1217 141 1497 531 824 840 1397 1152 1553 488 747 662 1496 1135 1375 701 1371 581 1369 911 1471 855 1041 408 685 1358 1590 413 1134 593 1401 413 1059 550 1306 304 965 139 368 454 1571 736 826 727 1171 490 978 224 1329 662 1366 1342 1551 1006 1439 197 513 365 1123 129 642 25 51 184 436 254 1460 1296 1376 889 979 1000 1517 635 719 574 1302 575 643 56 246 592 1486 627 862 347 674 364 1263 58 1246 290 917 62 1561 1498 1549 229 1427 90 244 154 315 1081 1130 1034 1419 1263 1411 426 848 51 1487 612 1117 192 624 194 1245 26 230 141 412 740 747 1057 1488 404 486 582 952 305 989 465 1418 36 1598 461 1071 1109 1508 544 741 200 487 …
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: 2434 531 1481 1790 1798 2287 1859 2386 1242 1840 1532 1861 2149 2155 1231 1541 686 1496 1030 2159 497 664 1229 1898 1193 2032 1026 1915 179 614 482 2299 458 869 486 2227 652 1447 429 2303 49 524 618 1281 504 941 1047 1440 823 877 666 2190 1061 1965 1842 2103 877 925 1464 1500 840 1777 2040 2220 49 1478 329 2420 299 1926 102 2096 356 2029 1043 1833 271 665 850 1332 427 921 1477 2309 1598 1672 848 2058 1410 1678 1064 1763 1028 1907 1070 1418 1920 2213 315 1817 688 2136 758 1262 483 1688 1238 1639 812 2067 716 1455 344 1364 156 1467 400 1608 1702 2427 623 1165 2054 2262 390 1829 281 1008 2093 2122 660 1904 5 2359 227 1205 653 1404 1346 1621 316 1734 382 1123 882 2082 1435 1858 822 2027 255 1401 1696 2109 435 1004 903 1886 508 1928 1217 1566 349 964 1331 2005 587 2290 196 1681 229 1800 1232 17…
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: 1321 2024 257 495 444 470 271 588 493 912 726 1143 179 1239 572 1026 140 627 1 825 554 668 249 382 395 559 971 984 189 286 269 376 971 1186 1 1156 195 311 360 760 367 384 534 666 308 1123 441 473 995 1143 331 969 144 173 134 775 790 869 332 502 196 1022 365 535 760 1087 302 547 56 271 485 961 835 1130 378 712 748 1134 19 276 283 1244 53 1276 1124 1178 387 924 372 892 1113 1215 355 608 263 1214 116 1161 804 866 111 344 296 681 577 1255 62 779 63 1012 1012 1095 619 660 323 1166 198 1184 156 727 193 1236 33 1318 446 1287 340 796 100 794 912 1222 64 413 419 665 171 884 672 1105 156 1255 365 1175 136 1138 759 951 207 964 251 543 509 541 781 1034 974 1218 146 1222 392 626 194 717 312 1237 281 358 203 347 735 1096 94 171 604 1126 131 1301 686 760 495 1014 108 756 399 467 577 1192 362 903 288 982 …
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 <= 3056; 0 <= m <= 3056.

Loading...
Test Cases:No test cases
No test cases available.
Ashen roads Build Order - MEDIUM Coding Problem | CodeTikki