CT62116

The canals at Sandspire

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

The council of the desert outpost of Sandspire pays by the answer, and Jatin intends to earn it. First: the full register of canals. 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 <= 797; 0 <= m <= 797.

Example 1:

Input: 361 225 107 118 82 248 223 325 43 247 139 219 75 122 76 304 208 275 55 361 54 242 115 334 124 229 130 294 227 282 34 223 74 163 74 306 103 314 206 217 31 117 67 321 116 133 30 144 102 343 48 128 213 253 75 271 12 310 244 358 7 80 284 337 158 238 69 291 134 305 62 269 256 301 196 211 106 181 236 343 113 230 273 336 271 278 316 359 156 281 87 131 20 57 212 290 145 261 34 304 236 248 178 296 44 105 53 69 290 348 138 234 66 130 114 178 161 217 85 188 61 200 100 305 209 293 63 346 165 350 148 350 97 344 133 239 19 331 21 53 51 180 159 264 184 218 71 83 135 322 181 266 10 215 69 73 98 233 127 175 77 157 288 331 200 233 104 174 105 359 82 224 60 238 83 142 326 345 97 297 100 227 7 151 78 115 114 285 59 229 151 250 196 223 154 228 201 257 72 239 200 281 55 239 68 347 23 340 293 300 146 224 173 225…
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: 309 407 179 221 187 218 101 260 30 213 160 198 12 168 194 270 148 160 177 249 126 235 23 174 70 278 11 259 194 290 17 197 96 150 49 205 122 220 184 214 66 233 87 136 36 234 40 221 81 220 55 94 156 226 11 37 229 261 15 267 79 277 285 295 93 200 24 27 18 232 124 199 236 282 65 107 18 215 157 274 222 254 62 253 18 177 264 296 13 261 33 108 33 210 94 158 45 152 180 219 166 242 208 283 89 290 67 118 155 232 127 302 184 257 70 142 115 292 212 213 104 176 66 238 54 146 155 262 171 175 102 295 22 126 173 180 6 125 1 283 71 180 159 225 284 290 35 165 92 143 118 204 47 240 134 144 96 101 19 258 19 89 6 11 77 86 74 276 229 294 244 308 200 254 125 290 9 59 6 83 72 138 140 285 88 219 118 222 191 288 3 59 115 299 37 254 41 284 5 298 20 114 61 273 259 282 45 134 84 212 134 273 40 249 214 266 1 164 179 20…
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: 10 45 5 9 5 7 4 6 5 6 8 9 7 8 2 7 3 5 1 9 6 8 5 8 1 7 2 6 4 7 4 8 2 8 4 9 8 10 2 3 9 10 7 10 7 9 4 10 2 5 2 4 2 10 3 9 3 7 2 9 1 2 1 10 5 10 3 10 6 9 4 5 1 6 6 7 1 3 3 4 1 4 1 8 3 6 3 8 6 10 1 5
Output: 1 2 3 4 5 6 7 8 9 10

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The canals at Sandspire - MEDIUM Coding Problem | CodeTikki