CT50825

The Umber Build Order

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Deep in the archive halls of Scrollkeep, Wade studies rows of bridges entries. One clean number will settle the guild's oldest argument. 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 <= 1050; 0 <= m <= 1050.

Example 1:

Input: 301 106 288 291 24 112 6 187 135 262 175 300 46 217 23 213 196 211 4 239 11 32 7 192 30 112 114 208 29 293 23 197 35 238 17 214 81 217 74 134 97 225 94 184 22 202 131 141 156 284 5 84 99 280 30 237 213 224 93 194 14 236 174 213 91 164 151 282 22 168 56 206 99 264 93 97 5 62 275 290 101 189 18 143 94 153 73 226 66 184 23 182 32 294 40 88 71 230 13 29 118 168 70 75 75 197 144 154 59 170 101 129 101 111 51 144 21 281 94 295 51 211 59 225 90 132 186 298 36 221 155 269 103 229 257 258 124 125 94 168 24 25 109 132 124 133 38 84 76 285 124 159 194 254 44 66 228 294 10 38 118 251 4 188 13 91 130 241 10 259 76 198 44 183 137 214 187 252 70 291 68 109 206 260 175 176 56 155 64 260 65 237 5 182 61 299 4 105 60 283 134 166 78 120 220 279 120 168 32 248 271 285 23 84
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: 46 1035 26 30 3 46 4 40 3 38 12 43 43 44 25 34 16 40 4 25 5 40 2 43 12 46 27 41 29 30 14 40 7 23 12 20 30 44 4 6 33 46 23 42 10 30 3 20 20 40 27 42 17 24 18 35 16 17 34 37 1 39 20 42 14 18 8 31 36 37 21 34 4 17 32 38 16 38 3 24 19 25 34 44 5 37 33 35 13 40 22 34 14 42 1 33 4 24 28 41 8 34 7 34 6 19 12 27 1 4 2 16 11 21 7 28 7 16 5 25 20 34 2 28 38 45 9 24 12 25 5 36 2 39 3 32 14 29 2 35 3 13 11 46 17 22 20 28 14 30 42 45 24 33 16 36 5 23 5 19 7 31 20 30 14 17 18 43 24 26 7 41 6 18 22 25 17 35 13 31 2 21 11 39 13 34 30 31 23 37 26 39 4 46 30 33 36 39 21 40 13 14 13 16 7 44 13 19 21 22 33 36 1 24 9 15 7 40 13 44 1 18 10 24 18 21 3 30 6 13 36 41 6 27 2 15 3 25 1 43 23 38 20 27 34 40 35 41 8 30 24 34 34 43 14 34 1 37 14 28 9 36 11 38 17 23 3 10 14 43 2 36 27 43 8 23 1 10 18 30 12 24 4 34 9 34 …
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

Example 3:

Input: 294 562 112 249 30 283 237 294 24 273 215 288 70 134 174 216 144 149 79 166 119 280 57 258 91 168 41 258 96 168 100 105 48 194 91 244 226 257 143 244 20 114 48 80 4 211 186 204 195 278 130 144 94 214 208 279 120 199 1 137 102 140 113 264 42 146 64 177 209 236 137 211 121 222 127 155 150 246 272 287 6 262 201 275 229 231 31 162 151 270 137 202 160 198 106 290 113 292 118 248 84 228 203 239 214 267 228 272 95 145 166 224 80 271 143 242 34 67 16 213 69 148 57 101 70 133 17 117 78 228 20 36 27 84 3 217 174 242 71 192 107 162 80 108 133 174 159 222 58 225 239 251 162 293 1 42 140 283 21 117 27 293 200 288 218 294 170 198 250 270 37 109 188 211 88 206 95 129 106 230 87 278 104 261 4 267 10 282 21 252 142 214 209 274 34 253 70 230 46 215 76 243 138 185 5 81 55 213 99 204 53 189 2 66 60 192 87 255…
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 <= 1050; 0 <= m <= 1050.

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