CT35526

Rosa's Ledger of bridges

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Caravans arrive at the ember mines of Cindercrag with crates of bridges, and Rosa the paymaster must account for every last one. 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 <= 3099; 0 <= m <= 3099.

Example 1:

Input: 348 203 49 91 66 76 88 150 43 310 39 259 209 284 112 209 30 144 35 40 43 146 94 102 100 127 189 310 23 30 34 286 157 187 79 109 218 263 98 155 7 342 88 274 146 303 80 304 138 198 136 183 53 56 87 182 214 322 146 231 12 313 160 225 138 185 20 22 176 313 38 124 116 206 171 222 97 149 49 101 147 324 151 204 58 301 97 266 307 323 137 173 50 132 94 327 264 318 61 307 205 320 185 224 49 301 241 246 168 266 244 342 85 284 62 314 178 197 257 291 174 248 318 332 93 222 11 112 81 284 50 336 157 249 164 200 105 198 161 221 179 184 19 64 34 331 12 234 41 308 26 264 275 347 109 206 310 336 137 263 280 334 83 169 2 23 16 322 193 277 244 332 193 319 31 309 65 262 50 307 276 296 60 283 314 340 16 307 201 229 278 285 61 222 93 274 237 323 40 67 21 172 181 309 23 40 129 205 14 274 311 336 15 245 263 303 104…
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: 2629 1974 188 1654 88 972 1530 2018 2057 2169 1148 1554 1629 1987 483 898 139 592 712 1006 617 2479 912 2507 689 1112 160 665 527 1006 547 896 34 2477 1008 2141 1520 2062 70 945 450 2158 822 1374 1602 2344 1605 2473 232 1234 52 1768 473 1674 1024 2228 1007 2349 231 1587 1025 1881 840 2325 1105 2402 754 1005 422 1348 983 1581 434 2489 702 1963 1454 1750 355 831 19 1286 103 2627 134 194 1 2017 345 2095 490 985 2122 2559 467 2028 332 929 491 1076 1409 2543 523 2483 2208 2378 829 2083 42 1178 48 164 873 1716 426 2037 1451 1489 853 1501 516 1102 711 1554 758 1833 301 414 1301 2439 226 2095 479 2409 592 1026 261 1173 1 1275 574 2051 649 2457 67 2069 280 1372 1080 1183 1250 1709 2068 2619 500 1255 2026 2178 117 313 147 1549 851 2033 741 2496 107 1199 697 1380 334 691 154 842 933 2110 1115 1849 16…
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: 2806 671 2085 2594 2492 2800 849 2301 727 1952 896 2415 499 1020 395 2355 2379 2662 1525 2319 637 2106 1132 2199 168 307 667 1096 1785 2182 2391 2568 1812 2488 714 907 1965 2099 330 1989 1668 2648 425 2186 1419 2761 1804 2500 950 1170 1281 2644 1937 2755 1420 1491 1797 2616 796 1050 1298 2738 1801 2069 1951 2672 1568 1779 75 1110 218 983 563 742 458 2688 732 1334 1467 1798 1279 1353 403 2386 151 1485 1786 2292 379 601 1050 1073 121 1685 1016 2187 1317 1824 314 1682 522 1481 1823 2672 716 732 1255 2068 302 2310 1061 2364 1972 2230 1412 1432 169 2622 170 1162 1438 1798 1865 2595 810 2005 2408 2636 468 1719 1401 2441 511 1599 868 2572 754 2442 1579 1637 556 624 566 1480 995 1242 1790 2618 163 1037 177 1082 567 2143 458 1707 2135 2449 2287 2434 2376 2416 688 765 1839 1875 1030 1504 1259 2468 7…
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 <= 3099; 0 <= m <= 3099.

Loading...
Test Cases:No test cases
No test cases available.
Rosa's Ledger of bridges - MEDIUM Coding Problem | CodeTikki