CT49255

The Ashen Build Order

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

The harbor bell rings at the garden city of Petalbrook; Kael weighs the day's tunnels manifests and starts the calculations. 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 <= 3538; 0 <= m <= 3538.

Example 1:

Input: 2053 2890 1448 1943 835 1284 1213 2000 179 1453 1483 1714 359 859 36 538 1454 2018 14 1902 1841 1914 935 1843 1063 1694 292 554 518 1820 275 917 167 469 538 1516 911 1175 673 974 620 681 1024 1396 947 1373 1929 2035 185 857 715 1054 744 783 564 888 15 556 241 797 541 562 396 1551 188 1924 425 1138 960 1590 1572 1914 685 1326 375 632 17 550 833 1876 683 2037 767 1846 447 1694 985 1207 1014 1493 245 478 1570 1988 1246 1524 517 1081 1605 1770 1222 1311 93 1177 67 644 1021 1528 559 1405 1531 2001 766 1932 421 659 631 1091 519 1790 596 910 1196 1404 188 390 21 940 37 1160 329 555 738 1299 15 667 263 2053 1436 1616 1014 1923 1318 2045 226 1956 521 1989 1528 1948 361 965 649 933 1041 1082 1307 2009 467 1015 239 1377 89 1821 1019 1279 1270 1927 69 1271 120 1394 387 1852 1153 1839 814 1877 308 318 …
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: 3382 3274 2023 2799 1802 1815 1464 2346 671 2480 820 1802 2540 3137 627 2568 551 1649 36 773 2312 2671 792 3377 942 1230 644 1266 571 920 354 3248 797 1750 1028 2718 1210 2068 1944 3172 997 1923 2031 2921 1152 1732 248 1187 2430 2601 2199 2940 614 3327 1721 2149 2750 3216 944 2106 1450 3016 660 1955 247 695 2545 2767 999 2110 295 1962 476 2185 1045 2734 1794 2782 594 1443 1596 2622 65 554 293 1568 809 1221 667 2097 1019 2837 717 2474 165 646 2753 3013 796 3114 2477 2696 1061 1824 21 3081 1565 2049 380 2767 2201 2228 548 2278 2066 2535 25 785 1403 1564 1039 2061 1577 2807 2475 3244 1315 3115 1609 2010 65 1186 2144 3268 2427 3220 869 2160 1144 2696 769 2617 564 2383 3 2697 2120 2329 232 3237 2957 3308 787 2478 309 2050 2258 2861 1994 2893 1792 3259 25 3279 1280 2883 174 1860 497 841 2023 204…
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: 345 2501 98 115 127 218 167 312 194 206 3 174 136 239 91 344 110 235 20 167 109 294 59 194 105 178 161 243 38 160 305 329 76 197 302 304 178 298 19 126 140 344 158 190 99 327 98 311 134 229 83 339 251 306 43 324 320 329 282 305 18 161 97 275 97 221 10 87 255 265 98 171 42 326 238 300 4 343 56 75 316 340 118 252 2 44 258 321 3 257 162 205 144 262 238 312 63 338 150 222 16 323 27 227 145 238 79 142 107 150 117 297 13 198 44 113 80 204 98 127 167 265 185 287 37 130 200 242 143 190 168 288 123 294 168 210 196 294 59 128 42 70 75 158 5 34 36 323 247 286 169 223 235 297 296 341 28 33 229 262 29 70 102 111 52 140 210 225 36 266 36 288 11 110 140 316 2 154 5 319 77 227 214 311 270 310 131 137 17 209 19 259 29 266 21 92 206 261 152 284 195 234 47 327 156 178 1 324 67 74 161 182 201 241 65 238 17 10…
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 <= 3538; 0 <= m <= 3538.

Loading...
Test Cases:No test cases
No test cases available.