CT48490

Farmer and the Build Order

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

At the fen lights of Will-o-Wisp, Farmer records each routes in a worn leather ledger. The guild wants answers, not guesses. 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 <= 3921; 0 <= m <= 3921.

Example 1:

Input: 315 1369 47 66 41 51 12 196 108 144 2 46 233 313 96 272 182 250 43 88 15 161 30 268 28 122 240 259 12 15 55 161 140 236 163 198 252 291 14 233 20 154 23 261 98 183 87 225 131 171 78 270 100 144 163 288 255 261 11 235 60 223 181 267 53 108 20 145 143 253 19 77 205 216 18 269 27 125 75 99 98 186 1 54 226 296 20 254 18 29 7 165 110 216 138 284 110 151 86 183 51 277 98 282 20 210 55 225 186 290 125 309 301 311 25 279 93 101 63 100 169 266 95 244 148 244 55 299 45 270 17 71 129 261 134 185 23 199 196 246 115 170 64 162 99 250 20 142 147 191 33 244 108 261 36 258 48 309 197 232 93 179 80 127 58 249 76 269 213 231 172 259 180 279 75 241 122 148 200 225 186 309 3 109 86 272 50 52 38 235 43 137 37 181 252 274 183 303 135 188 139 203 277 293 9 292 36 270 92 192 116 274 266 269 189 190 107 108 77 189…
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: 3575 2849 3009 3245 553 950 212 1592 667 3081 1195 1261 637 2550 662 1409 991 2870 1137 2947 273 2063 1120 1745 1805 2741 425 1912 1072 3461 358 427 3070 3328 1453 2789 2289 2399 1132 1234 2890 3222 810 1461 3043 3382 361 1550 730 2131 22 2531 3078 3558 252 3301 545 1957 757 3006 1445 2169 587 984 1 1772 795 1204 558 2561 2758 2858 997 2016 1100 1218 922 3318 131 1129 2846 3514 644 1582 1776 2229 2276 2983 271 1606 237 2312 1322 1324 52 3027 108 554 2097 2821 1295 3262 1189 2083 90 3502 306 2115 997 3561 430 1786 63 3207 1247 3399 2585 3061 2584 2669 465 2561 453 3234 997 2588 696 1357 3314 3325 2795 3443 2104 2974 227 2313 135 2567 716 3085 42 2997 2628 3190 810 1730 2772 3109 1095 2102 1544 2246 577 1993 591 2706 3287 3563 2252 3138 1242 3120 224 957 80 2573 698 2155 2600 2743 1136 2395 …
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: 2643 3102 236 1041 400 419 1084 1782 635 1420 1706 1794 1933 2322 117 522 2211 2615 263 590 1519 1800 417 1741 96 1542 385 1691 518 1589 1029 2635 2086 2510 950 2061 1214 1582 417 2035 742 1825 1380 2465 1447 1961 197 2214 292 461 1880 1972 2009 2605 1570 2154 2456 2546 90 2448 659 1146 964 1618 446 660 1664 1802 1701 1889 2268 2293 1671 2502 1359 1684 855 975 341 1983 582 1650 751 2131 214 2414 210 1741 2048 2622 1235 1546 411 888 275 564 486 774 243 327 254 1260 15 2512 947 1015 1720 1905 2088 2357 1417 1418 1484 1561 317 443 719 2426 1033 2129 1514 1573 564 2200 1212 2182 1205 2275 1725 2546 647 2567 590 1235 260 2211 176 894 345 1973 137 863 544 1256 190 2150 123 754 857 888 1205 2458 1920 2180 1771 2261 2315 2486 285 1686 279 1569 55 1459 2308 2620 192 2112 875 987 1459 1491 2 2137 38…
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 <= 3921; 0 <= m <= 3921.

Loading...
Test Cases:No test cases
No test cases available.
Farmer and the Build Order - MEDIUM Coding Problem | CodeTikki