CT54554

The Brasshaven Build Order

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Legend says the vault under the old quarter of Brasshaven opens only for a perfect tally of bridges. Kian means to find out. 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 <= 2791; 0 <= m <= 2791.

Example 1:

Input: 550 34 282 452 7 288 44 549 78 361 67 502 188 231 24 361 71 465 357 529 98 507 367 425 343 415 360 394 169 416 53 396 197 367 273 289 242 380 320 373 185 195 400 500 316 348 269 447 524 528 287 509 2 431 41 431 2 163 61 427 324 382 59 106 238 428 117 333 125 389
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: 177 1417 81 142 34 48 3 61 82 127 79 127 21 64 132 163 27 71 113 176 22 167 33 46 87 141 55 148 122 164 64 108 51 143 54 139 1 65 89 107 38 130 23 103 49 129 133 177 3 62 61 128 142 143 85 160 17 33 33 81 65 134 19 81 7 81 42 154 124 126 86 140 92 153 95 100 6 106 11 107 37 130 99 160 15 117 60 135 40 116 121 175 36 93 4 87 14 98 68 75 78 119 23 148 68 130 37 39 3 66 75 162 38 96 83 99 129 154 39 94 100 161 18 114 27 173 71 136 6 102 109 142 27 153 82 158 126 142 138 174 83 129 6 150 2 117 135 140 79 123 155 168 20 161 81 177 61 164 101 142 79 93 35 168 122 140 3 126 11 170 86 111 25 33 43 93 34 112 146 147 39 73 129 175 7 106 83 154 48 59 39 170 69 138 107 119 89 169 20 74 57 95 97 102 41 63 53 172 62 169 83 138 32 72 48 161 7 55 50 110 44 117 138 143 36 99 5 99 66 168 93 150 57 65 10 91 …
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

Example 3:

Input: 2458 1622 639 1967 955 1551 1163 2305 618 2271 775 1866 283 2105 979 2107 401 882 1359 2099 1083 1913 316 1261 519 822 1345 2453 1812 1850 1637 1893 533 1888 1762 2323 766 2228 932 1613 680 2183 1085 2174 1939 2006 1813 2008 404 1626 455 1305 690 1935 589 2205 864 1281 1874 1896 994 1155 240 1636 340 463 1533 2227 13 2185 271 1675 311 1633 1445 2358 241 1294 1230 2298 1121 2373 1949 2443 1700 1804 1252 1463 1224 1577 2285 2350 445 2431 1695 2184 1676 2240 10 321 1819 2126 1154 1330 1943 2189 192 474 1076 2296 1018 1341 462 2311 340 2236 41 921 595 2209 1278 1394 428 686 754 2347 172 1817 441 2223 373 1004 1269 1347 2178 2410 485 1608 761 2409 1398 1474 817 2111 348 525 373 1648 1081 2206 398 1508 696 2368 595 2440 804 1042 859 1326 2084 2305 250 2082 1999 2276 1672 2320 1427 1876 1283 1655…
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 <= 2791; 0 <= m <= 2791.

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