CT50443

The Build Order of Barkhaven

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Leon inherited the kitchen at the cork grove of Barkhaven along with its curious bookkeeping system for canals. Time to make sense of it. 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 <= 3554; 0 <= m <= 3554.

Example 1:

Input: 1298 1740 956 1109 455 971 50 965 107 1298 236 760 298 368 147 273 349 868 223 362 31 998 581 1165 349 494 681 1013 537 857 834 1111 1082 1186 247 970 887 1114 375 1023 151 981 566 897 621 1172 222 1222 449 626 444 525 427 544 3 1261 127 1161 659 1245 417 1122 1136 1264 416 1121 380 891 737 1078 839 919 37 500 449 842 418 972 975 1202 201 631 382 802 138 430 574 842 11 751 319 953 732 1053 534 644 14 634 934 996 586 619 865 1121 1015 1176 458 842 11 613 386 1051 166 281 111 225 293 827 617 935 389 1022 156 287 175 471 304 1134 519 948 473 492 295 1204 96 1209 100 290 648 665 441 1172 242 971 286 933 43 1138 578 759 10 473 22 651 273 865 310 313 30 77 567 1073 802 1225 59 1149 704 1067 731 1277 1 102 112 1276 568 1008 642 1290 926 1061 1130 1196 561 1159 449 1195 535 677 199 465 700 1092 81…
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: 166 2365 16 30 117 147 24 164 64 117 42 104 9 101 75 93 42 122 79 94 8 113 117 139 21 47 45 53 24 123 26 131 105 118 63 156 31 140 137 143 88 115 16 101 21 40 18 146 3 17 9 139 29 64 19 88 67 122 48 153 34 107 63 140 119 142 3 82 3 41 23 149 76 141 50 133 83 118 23 65 154 159 4 88 73 134 77 138 30 45 97 123 33 38 35 86 107 160 14 146 19 151 15 111 5 142 27 44 98 156 104 147 80 131 2 20 103 125 72 77 34 39 59 83 18 26 62 101 54 81 94 120 6 28 81 147 10 82 71 136 21 139 39 96 57 86 70 140 57 146 15 71 58 92 52 62 35 165 14 129 35 38 30 41 26 56 27 65 6 56 17 47 83 147 66 71 57 80 129 156 84 149 60 105 4 62 14 83 125 162 27 149 2 58 114 145 9 94 94 99 20 115 59 164 4 13 54 60 48 55 9 104 109 130 109 140 120 166 28 85 27 108 6 126 10 129 7 117 81 108 68 72 19 112 119 127 22 82 87 116 116 124 1…
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

Example 3:

Input: 2835 3295 1002 1193 213 2744 648 670 1697 2371 1510 2532 613 2210 954 2071 178 541 1034 1471 1649 1979 1242 1895 1164 2119 1711 1846 17 2105 97 1893 962 2407 733 2475 713 2749 164 2594 328 1979 441 1579 1687 2049 1310 2674 1626 2402 83 2224 1387 1645 2401 2726 180 2265 166 1862 37 2050 63 2023 717 1125 1356 2494 819 1790 449 1188 238 725 653 1260 1120 1650 1719 1856 1515 1912 413 1054 955 1388 1431 1716 376 2677 638 2495 98 2807 2193 2382 1394 1833 1026 1689 938 2667 53 374 1203 2816 1481 2591 1416 1761 1195 1927 1702 2039 1530 2577 1348 1882 1789 2189 878 2581 247 1716 2033 2392 484 2673 366 2791 1029 2102 1063 1830 21 1158 1951 2707 965 1093 239 1607 1653 2606 2007 2680 1108 1967 1126 1730 1146 2784 334 2714 525 1131 2490 2701 215 1034 323 2692 507 896 823 1314 2453 2820 2708 2788 1498 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 …

Constraints:

1 <= n <= 3554; 0 <= m <= 3554.

Loading...
Test Cases:No test cases
No test cases available.
The Build Order of Barkhaven - MEDIUM Coding Problem | CodeTikki