CT37051

The tunnels Build Order Puzzle

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Before the gates of the cliffside roost of Stormrest close for winter, Jatin must finish the tunnels ledger - one figure at a time. 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 <= 3775; 0 <= m <= 3775.

Example 1:

Input: 197 307 10 149 35 109 67 152 123 172 181 185 73 148 145 171 5 6 55 139 46 191 158 167 42 44 135 153 19 133 109 166 95 193 64 96 103 126 13 109 162 177 38 70 19 109 38 111 73 133 4 66 74 79 42 154 114 166 36 99 163 184 31 128 81 95 14 185 42 92 14 25 107 157 156 159 3 71 54 144 62 65 76 82 139 150 42 47 129 195 1 61 56 72 62 159 83 106 103 124 78 134 79 183 97 175 2 95 66 181 167 195 49 164 70 96 51 134 11 42 11 60 62 142 48 106 136 160 45 177 158 171 5 89 10 145 166 186 76 109 3 35 74 102 17 183 8 126 121 184 20 158 85 103 90 165 133 184 116 170 48 78 45 152 9 85 67 140 100 168 36 59 57 157 16 182 35 55 128 134 164 182 2 186 106 123 58 180 72 131 113 189 84 188 167 196 18 54 48 191 5 34 1 63 30 143 25 126 40 110 34 70 51 83 118 191 81 141 8 173 11 16 8 15 21 152 110 194 97 184 88 180 24 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

Example 2:

Input: 3768 3754 986 2540 617 3131 1153 2117 883 2134 492 1662 967 2287 2085 3544 2195 3649 52 805 2595 3453 602 1708 2015 3179 178 3425 2345 3620 150 1329 275 3574 1398 1567 2248 2584 392 665 2045 2462 256 2260 3325 3730 976 2963 2089 3218 1206 2787 1381 1438 282 2321 715 3142 462 1853 1392 3445 72 1314 1429 2358 1149 2895 2102 2472 339 2279 1204 1836 82 2998 1572 3204 535 2164 557 2813 1680 3575 1430 2885 576 2346 1060 2296 590 3337 388 1917 860 1337 1134 2160 1195 3215 1980 1987 2322 2889 897 1614 1626 1869 451 2504 170 1293 197 1574 56 2518 82 3099 1788 2746 930 3430 1484 2941 1861 2249 196 3258 1970 3351 2959 3499 998 2291 526 3483 1397 3507 49 3303 1157 2646 868 1126 1341 2819 3423 3717 36 602 468 1581 2842 3221 338 3404 2603 3531 835 1630 603 1338 526 3442 1070 1767 907 1615 1246 2300 1231…
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: 2993 2855 447 2341 55 1594 334 680 523 2368 1262 2922 12 2458 540 1125 699 1740 1611 2217 1335 2943 12 1691 842 1253 5 2825 240 852 1363 1514 1796 2432 77 155 1887 2805 275 2326 1358 1404 288 691 78 1092 836 1271 133 2664 481 2962 726 1803 256 371 517 866 1238 1430 1211 1633 397 2559 1151 2926 1813 2283 2566 2952 278 1013 1214 2467 1213 2830 625 2385 365 2978 584 2304 5 1952 496 628 290 1654 1540 2567 46 2703 1866 2216 192 946 24 2277 623 1184 141 700 675 2480 1621 2358 941 2295 737 1199 606 2493 1173 1995 630 2199 376 1497 154 2526 998 1745 7 652 1604 2932 134 2578 775 2716 92 2898 1395 1668 1064 2261 320 2753 1765 2237 895 2454 325 2305 998 1416 320 2973 667 2432 54 299 2148 2484 219 1933 314 2636 104 1915 425 1903 886 1926 1378 2236 811 1050 956 2904 863 1942 2479 2941 236 611 1060 2551…
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 <= 3775; 0 <= m <= 3775.

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