CT35886

The roads at Grapehollow

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Morning light hits the terraced vines of Grapehollow as Nyssa unrolls the day's manifest of roads. The tally will decide the next shipment. 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 <= 3777; 0 <= m <= 3777.

Example 1:

Input: 3650 1992 83 2504 2028 2870 449 2303 1821 2503 1468 2384 14 2667 796 1710 803 1836 2720 2843 2051 2598 1900 3511 961 1171 1248 2181 362 847 327 814 270 2552 325 2115 1404 1776 552 875 200 939 2735 3272 1983 3039 476 2418 1288 2303 304 1470 648 1588 178 988 175 2906 2384 2540 713 2280 849 3390 69 236 814 3642 1431 3422 1462 3538 22 2436 1306 2128 90 1285 1694 2241 3285 3360 2636 3070 674 2126 999 1767 733 2785 1961 2022 1626 2768 2452 2938 1042 3256 699 2586 1151 2858 526 2204 3188 3466 570 2920 2194 3430 916 2948 3199 3265 1521 2108 130 2023 1970 2662 2658 2819 967 2092 1356 2087 40 482 2788 2888 692 2528 1640 3218 1043 1158 288 1055 572 584 1022 2392 150 685 1325 2289 434 1722 385 1337 663 1569 1860 2937 2309 3051 587 2592 680 830 1311 1430 1103 2235 1 625 465 847 1430 1749 2621 2661 1061…
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: 3287 3017 970 1804 1279 3091 800 1319 2187 2592 1395 3213 932 1299 2487 3080 979 1474 1714 3005 307 1643 361 2075 643 2101 214 1209 3025 3202 105 3226 831 2841 1156 2128 60 1512 2004 2065 168 724 1671 3221 169 2575 1267 1547 1010 2387 747 1850 1548 2644 600 870 112 843 1784 3029 689 1763 328 2903 556 1862 359 2980 903 2349 1489 2468 1713 2713 1672 2081 1391 1591 1651 1759 1792 2999 440 1626 1086 3189 1380 2433 1057 2316 474 2031 8 819 905 1346 2473 2831 1730 1923 1810 2987 555 2331 1182 1432 327 1266 1319 1584 1693 2139 149 1878 73 1384 596 2344 760 3130 959 2503 474 1326 291 1032 1114 3225 1429 2365 2035 2107 67 930 1649 2763 413 1720 909 3185 1850 3231 782 2241 2124 2520 1045 2661 2102 2175 1259 1983 1146 1200 2003 2540 1480 2395 432 1690 2037 2434 936 1364 1611 1824 347 1532 2065 2859 3…
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: 629 171 16 169 37 315 328 474 189 325 107 313 22 463 346 386 180 232 333 524 345 407 411 612 34 313 490 506 351 591 19 328 129 396 49 553 28 405 287 432 95 458 202 414 98 330 44 399 316 326 174 600 16 228 41 501 464 607 26 148 225 620 513 626 410 629 232 576 311 402 406 515 423 482 41 408 479 613 252 414 308 592 25 95 125 475 204 441 131 550 106 388 230 390 205 440 124 440 82 188 21 252 557 601 136 215 284 492 251 385 139 458 40 319 53 510 163 270 8 228 114 119 419 620 49 230 369 490 152 466 235 312 27 608 217 493 297 586 227 547 86 90 261 621 129 326 118 347 476 522 243 373 144 575 393 559 35 347 137 533 240 313 45 306 321 601 248 409 228 278 20 27 18 595 237 324 179 392 269 580 107 455 60 577 457 594 276 279 387 431 447 463 128 199 353 552 124 464 12 366 38 271 515 601 465 610 203 375 11…
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 <= 3777; 0 <= m <= 3777.

Loading...
Test Cases:No test cases
No test cases available.
The roads at Grapehollow - MEDIUM Coding Problem | CodeTikki