CT46787

Xanthe's Scarlet tunnels

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

The quartermaster Xanthe has been asked to inspect the delivered goods. On the desk lies a long table of tunnels readings. 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 <= 3061; 0 <= m <= 3061.

Example 1:

Input: 558 1351 344 394 6 463 46 268 161 558 245 520 70 89 79 380 270 336 246 483 57 306 92 108 56 120 292 551 35 43 268 532 22 162 151 285 28 558 71 460 236 550 98 401 274 431 176 442 73 315 457 506 129 201 248 413 120 459 71 455 228 529 269 335 256 276 501 507 10 539 77 318 162 349 91 305 87 342 36 556 281 387 296 407 74 417 474 527 260 353 34 359 284 517 135 206 87 278 239 486 57 346 90 243 307 397 253 362 214 285 34 456 257 295 321 549 354 433 36 333 3 97 366 457 119 402 300 383 51 248 474 490 360 405 162 411 62 403 76 472 33 480 435 452 195 501 355 460 171 245 362 404 56 529 224 471 61 113 190 465 77 417 394 463 355 474 188 328 361 405 442 545 230 410 103 362 395 452 24 404 434 528 99 341 38 78 237 324 301 514 76 85 278 490 149 357 233 380 527 549 148 229 61 102 9 234 288 341 287 480 76 447 …
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: 2543 3019 199 2371 853 1285 513 875 287 1198 1675 2008 254 2066 79 800 1146 1838 1280 2345 552 715 460 1508 460 1866 188 499 470 1908 930 1868 309 570 476 511 440 2398 1045 2515 1253 1697 179 2439 2354 2509 697 1807 1055 1953 829 1847 495 1840 551 758 601 1567 297 1604 211 628 128 1058 23 2240 1934 2540 1799 1869 697 2214 706 1587 1805 2236 348 1636 781 1846 301 1198 773 858 404 1419 2150 2431 676 1389 27 1418 1278 2315 892 1322 237 2345 1699 2403 678 1946 1142 1851 222 2485 428 843 95 1647 560 1301 685 2485 185 1698 926 2305 346 617 1106 1556 642 2144 1078 1797 230 1715 1601 1672 309 1355 284 1585 690 2145 923 932 1551 1622 1649 2058 202 2199 574 1994 336 2543 512 696 1082 1151 1581 2091 196 1493 514 2523 755 865 285 1727 623 1598 566 1725 310 1014 257 2301 905 2443 1346 2153 87 429 474 2…
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: 2850 55 1082 1245 335 523 1307 1327 1415 2703 1334 2352 666 1076 147 1373 395 1748 2584 2612 1806 2479 1698 1711 1342 2070 1700 2600 234 2024 946 1225 2082 2151 1377 1876 2166 2689 674 1006 1748 2116 119 427 1178 2303 2034 2407 2125 2665 1834 2549 751 934 65 650 891 1863 2113 2378 547 736 933 1882 2309 2515 1763 2780 2504 2651 750 2011 837 992 182 985 169 1804 1212 1981 594 2545 1494 2823 364 2838 2266 2603 1365 1894 704 2389 522 787 474 542 1042 1688 1616 1674 964 2458 914 2070 2168 2591 1106 2432 522 1333 1146 2198
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 <= 3061; 0 <= m <= 3061.

Loading...
Test Cases:No test cases
No test cases available.
Xanthe's Scarlet tunnels - MEDIUM Coding Problem | CodeTikki