CT35923

Eklavya's Ledger of tunnels

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Caravans arrive at the opal reefs of Shimmerdeep with crates of tunnels, and Eklavya the scribe 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 <= 3564; 0 <= m <= 3564.

Example 1:

Input: 2954 1519 2602 2944 1401 2136 1722 1995 57 2679 1943 2695 73 1798 158 196 428 1995 2109 2655 1304 1492 503 2192 504 2063 1389 2245 4 1047 2131 2751 879 2567 540 2184 114 2706 2522 2632 322 2155 928 2087 40 2043 1637 2328 851 2475 291 2252 682 2591 975 2034 1376 2243 1934 2827 670 1550 1070 1990 62 235 660 2194 762 886 1940 2880 1713 2866 220 1470 675 2615 403 1363 922 2423 531 650 1065 2653 1917 2465 1254 2116 610 1851 155 2180 671 1128 1536 1554 953 1238 161 2201 609 1640 580 1079 468 2228 489 2467 551 1044 868 1464 616 1528 397 1484 605 1356 1376 1718 978 2048 234 2820 1053 1293 960 1002 2122 2137 842 1379 1698 1817 15 1429 218 2321 49 621 1551 2877 592 1364 2034 2243 295 2653 181 2105 443 2005 1228 2866 723 974 1713 1894 2599 2707 1533 2339 1 514 421 1743 49 776 2475 2579 1355 2895 714 …
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: 2999 2288 622 2016 682 2417 784 799 994 1588 1109 1858 1916 2278 1684 2751 488 2536 838 2670 2579 2842 523 2400 1142 1768 362 907 1245 2853 1783 2192 452 2680 870 1462 1758 1956 673 1757 2277 2583 1171 2210 624 2617 458 507 2119 2429 1391 2317 497 669 1423 2512 1737 2193 2038 2642 1800 2006 1917 2967 13 324 991 2125 1318 2131 379 1370 456 1848 833 2969 751 1554 564 1422 365 2607 317 1696 1069 2921 978 2449 426 1347 1456 2923 1435 2614 347 717 396 2297 1158 2743 1789 1898 886 931 782 1349 183 1756 912 2671 2080 2993 547 2603 629 2693 6 754 2443 2936 1233 2959 580 836 442 2219 2672 2965 239 1591 1633 2327 509 635 475 2946 1774 2984 1518 2705 494 2290 1158 2138 2418 2799 213 2591 560 2922 1673 2682 72 352 2324 2382 307 901 1963 2846 145 1507 2594 2753 754 1071 214 2132 2491 2634 802 2139 310 …
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: 561 2651 73 248 201 247 104 206 235 497 21 339 302 316 181 332 366 447 135 435 169 435 227 366 271 328 211 214 2 333 70 519 383 387 191 250 225 327 330 513 121 346 45 75 273 278 120 427 168 461 48 514 545 561 145 391 362 510 90 520 172 277 65 362 25 487 180 252 200 489 137 380 59 281 127 229 189 392 342 452 291 460 264 440 170 238 300 307 404 506 312 538 216 505 225 528 5 201 10 103 57 483 389 542 22 412 34 282 91 222 9 461 297 415 159 204 508 555 165 298 287 543 5 132 160 392 277 281 83 516 53 229 114 368 451 470 195 323 7 372 166 408 175 492 71 156 94 247 133 398 219 353 90 448 195 386 225 416 171 476 99 546 178 465 218 539 46 398 4 29 93 499 237 509 244 428 128 432 46 496 220 426 96 459 4 536 254 456 50 447 306 448 240 286 105 344 35 479 22 201 349 510 308 323 119 528 193 397 80 337 27 …
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 <= 3564; 0 <= m <= 3564.

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