CT38415

The Saffron Build Order

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Before the gates of the basalt cliffs of Obsidian Shore close for winter, Ulrica must finish the bridges 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 <= 2532; 0 <= m <= 2532.

Example 1:

Input: 2512 2337 1408 2176 1204 1530 329 2484 1723 2070 1091 2275 1511 1982 1196 1267 544 2162 627 1773 455 2044 1278 1694 860 2263 1022 2108 183 1159 396 2478 53 1449 608 2293 472 1683 836 2088 628 957 650 2473 1053 1364 769 2481 117 1687 2021 2435 1694 2081 292 1686 1146 2348 1667 2159 175 580 813 1297 1154 2502 426 2335 1426 1890 404 2426 733 773 1174 1532 40 996 153 1696 1461 2247 1901 1937 59 2391 976 1582 758 1870 429 1306 257 2289 436 2466 624 1348 1130 1683 734 2315 812 1183 90 1061 472 1399 694 1219 960 1632 230 1021 879 2099 487 2374 2317 2398 464 2350 553 1218 180 2467 473 1101 633 1269 890 1008 284 498 483 1347 487 1979 1724 2216 1275 2304 1395 1514 1546 2361 445 965 1329 1522 353 1857 193 2021 384 1061 694 1046 414 2469 904 1287 310 2292 437 978 545 1412 116 192 39 689 174 1253 2237 …
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: 1518 254 673 1143 1066 1230 14 627 537 618 455 810 460 883 1280 1450 1159 1483 293 514 135 415 427 1448 1440 1481 700 1416 1263 1431 90 1266 999 1044 336 581 672 1466 425 487 679 877 794 798 274 726 269 565 432 546 156 471 787 1278 70 851 289 1227 95 757 1381 1479 1054 1330 483 1368 152 429 767 1107 778 1374 505 1467 292 1104 279 644 655 1277 20 884 1006 1062 1043 1212 214 1485 809 1433 233 857 672 1283 37 1306 1091 1465 461 923 390 552 198 1142 391 532 124 472 548 568 494 1315 754 760 418 450 618 1456 1058 1147 506 824 667 1014 204 1336 513 920 90 674 203 579 585 1196 739 1401 389 816 362 600 471 1066 1166 1218 356 692 530 1135 40 580 326 1019 52 97 106 1307 173 1240 14 1276 898 1449 161 1014 251 538 388 984 1028 1344 425 1430 659 1010 18 242 47 1111 450 1450 954 1257 10 821 1285 1406 996…
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: 2290 1278 573 1337 637 1537 1137 1870 1272 1322 191 338 485 941 1324 1684 11 668 875 1793 29 1772 1727 1889 16 1256 1654 1724 36 924 1686 1919 1206 1269 331 2253 54 326 881 1741 523 1362 846 1456 271 703 276 936 329 905 1388 1589 1362 1754 693 2099 1212 1476 2050 2178 231 1529 2064 2098 955 2130 1483 1528 1155 1509 52 621 1259 1955 2162 2184 484 2207 721 1002 664 1278 891 2057 1639 1685 265 1831 1229 1873 651 2048 363 1842 1263 2203 42 585 1361 1747 494 1273 1468 1726 666 966 570 901 749 1823 1038 1519 92 1450 860 1972 1512 1828 1144 1416 62 1448 1915 2090 665 1057 1147 1642 1523 2131 283 1182 1438 2005 3 339 890 1068 1673 2250 782 1336 230 1411 952 2232 72 437 525 1447 75 772 176 1397 1412 2054 997 1737 974 1035 1567 2106 2006 2068 193 990 1014 2109 1414 2201 154 1141 920 1239 916 1580 27…
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 <= 2532; 0 <= m <= 2532.

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