CT53161

Last routes of Yara

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Yara found an old ledger of routes in the ferry office attic at the honey farms of Buzzwell. The margin notes pose a precise question. 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 <= 2993; 0 <= m <= 2993.

Example 1:

Input: 1301 244 846 1092 343 407 556 1107 50 769 425 791 820 1255 244 872 30 1225 1076 1240 585 869 555 670 847 868 438 1169 48 1072 996 1205 961 1236 644 1128 152 214 298 741 97 388 246 1153 23 1225 315 614 431 854 282 937 131 1015 161 828 755 1227 52 725 690 1134 20 1155 156 1027 354 759 110 443 160 702 637 901 448 679 319 745 1 374 899 1138 842 998 467 1299 449 1068 390 397 420 887 82 475 848 1172 1143 1212 173 812 168 803 521 555 496 516 127 896 273 482 478 1044 277 488 184 860 726 901 1217 1274 726 1004 971 1243 151 389 820 980 33 115 10 107 266 675 925 1040 743 1240 205 890 406 596 17 471 419 692 4 716 665 1158 359 1019 377 1177 65 672 290 553 115 793 337 456 641 1154 30 311 393 811 163 391 793 864 94 161 353 404 588 1218 487 507 1136 1271 572 608 210 1056 812 1086 324 790 244 403 815 1213 …
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: 85 265 17 68 32 69 26 58 36 68 33 55 58 60 33 34 1 68 8 39 45 57 68 72 9 70 53 77 52 65 7 78 14 54 24 38 57 58 7 77 13 77 68 84 51 63 35 64 20 63 22 55 56 67 57 65 5 35 16 31 34 60 12 48 21 81 47 50 3 25 10 73 51 84 68 77 18 70 67 78 14 30 21 82 18 63 11 43 34 84 15 75 72 81 3 7 49 75 39 57 36 69 5 65 16 37 15 51 41 44 43 78 29 43 10 36 6 35 61 85 38 78 63 76 59 69 59 64 7 49 23 73 37 55 59 61 54 71 22 74 17 18 27 57 60 69 64 68 16 62 1 41 24 85 48 55 33 39 45 63 11 67 56 70 9 29 1 17 50 70 4 47 30 61 69 70 4 27 55 85 57 76 16 44 42 68 53 62 47 51 75 83 40 85 35 62 2 23 11 45 13 72 20 75 4 36 8 49 31 44 46 81 15 78 11 76 21 31 17 26 26 54 44 57 3 58 37 68 63 84 44 82 19 81 14 20 66 84 49 76 20 35 13 36 3 48 10 47 43 70 6 38 37 63 59 60 38 77 28 57 60 66 18 32 27 46 22 66 10 43 10 31 64 67 …
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

Example 3:

Input: 2922 764 2143 2182 708 2352 767 1141 367 2695 1244 2758 775 1208 312 2007 1165 1968 1885 2889 1523 1860 1630 2306 2016 2692 175 311 279 2467 2155 2749 1657 2808 373 1625 1205 2194 623 1841 1908 2608 857 2329 404 2918 93 2665 1372 2045 1022 2636 797 1763 352 1744 132 279 432 634 2029 2219 2363 2513 264 1404 402 1734 340 560 799 1755 1355 2560 1048 1325 144 1220 1222 2443 1746 2823 1890 2914 1574 2633 850 1695 1064 1460 760 2484 1068 2908 1441 2812 1076 2250 218 2199 671 1243 260 1886 376 996 809 2300 871 1636 1357 1515 1096 2561 1878 2802 974 2032 1724 1953 907 1374 363 547 307 2141 585 1676 2250 2837 312 2732 11 2310 769 1739 58 1120 1957 2614 946 1334 401 2160 1737 2488 612 1391 1445 2157 907 2834 1043 2875 888 944 628 1037 859 1376 679 1336 2065 2761 206 1764 1218 2571 722 2151 728 2325 …
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 <= 2993; 0 <= m <= 2993.

Loading...
Test Cases:No test cases
No test cases available.
Last routes of Yara - MEDIUM Coding Problem | CodeTikki