CT50741

Last bridges of Seth

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

The harbor bell rings at the steppe camp of Horselord Plains; Seth weighs the day's bridges 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 <= 3687; 0 <= m <= 3687.

Example 1:

Input: 3433 1763 2083 2100 12 469 1315 3260 60 1798 261 3265 2715 2873 1291 3367 1584 3389 1019 2447 884 1134 274 2448 1936 2074 1369 2308 2386 3374 864 1735 2634 2906 1917 2047 237 1453 305 1808 3025 3310 1942 2179 1935 3151 395 2716 1972 2850 1341 2099 702 3267 1461 2035 1036 2596 202 1719 1299 2353 1128 1572 1213 2960 2600 3016 1220 3432 458 1786 2866 2973 805 1136 2007 2603 1584 2832 670 2565 1581 2246 1083 2197 1943 2517 763 2302 436 2784 2708 3372 2710 3246 1033 1588 981 2131 1641 2891 1707 1986 1309 2368 532 1583 1307 1885 2200 2943 1995 3295 619 1192 1020 2148 2929 3208 982 2124 2959 3174 838 1108 625 1475 287 1146 187 1046 1962 3300 459 1318 2103 3208 958 1170 1230 2427 1976 3009 2784 3279 519 1655 507 1993 2156 2581 1149 2783 276 1662 1905 3347 1216 1992 1141 2890 3038 3052 1538 2614 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 …

Example 2:

Input: 3477 559 712 816 262 1477 3143 3467 480 2058 834 2822 1790 2519 1223 2217 2925 3368 2506 3298 675 1773 1338 2106 2756 2823 582 1202 1140 1922 225 619 203 1662 681 741 1347 3097 1347 2059 2530 3356 197 879 205 1348 2129 2410 1049 1426 2156 2671 1970 2166 1934 2792 210 3232 2335 3266 293 2320 1649 1783 1650 3155 1612 2853 2748 3317 2823 3223 1130 1825 2397 3359 98 617 1577 1732 563 3225 1881 2545 836 2434 2332 2684 1687 2313 428 3394 2041 2835 2246 3411 2737 3189 1800 2120 144 2494 1742 1935 875 1964 1165 1332 2742 3405 1713 3100 1023 1706 1499 3009 748 2901 247 639 802 1362 78 110 2182 2758 100 3359 102 2287 2006 2821 682 1126 1331 2912 1837 3069 986 3082 1250 2521 672 992 1226 1270 975 2585 1202 2368 573 1570 160 2619 23 2168 981 2487 1762 2029 1151 1276 1331 1390 809 858 1586 3256 2575 32…
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: 694 3541 111 269 24 444 459 597 71 525 180 370 16 347 79 468 470 571 203 238 379 651 186 690 3 255 456 628 74 353 202 281 13 214 227 608 144 147 31 403 74 439 478 539 148 475 38 180 129 575 395 436 388 557 440 616 559 581 164 654 170 390 124 427 201 251 2 70 590 607 484 534 503 646 95 559 345 556 505 587 111 611 27 237 388 469 3 632 15 606 134 553 279 360 276 637 82 486 79 595 394 566 182 597 125 587 369 376 407 492 392 505 104 587 516 551 94 644 264 348 242 671 419 572 575 622 291 395 263 672 136 167 120 652 407 455 229 283 286 468 376 674 395 639 543 684 63 235 336 391 595 682 579 676 388 558 13 394 188 618 174 207 268 340 235 284 110 230 304 614 20 496 308 554 367 523 64 94 176 624 504 584 154 578 74 512 105 578 296 368 74 230 68 326 132 160 668 682 78 510 377 523 16 391 7 610 153 213 1…
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 <= 3687; 0 <= m <= 3687.

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