CT59178

Ysolde and the Brass canals

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Legend says the vault under the island market of Coralcove opens only for a perfect tally of canals. Ysolde 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 <= 944; 0 <= m <= 944.

Example 1:

Input: 604 59 100 302 31 244 40 205 302 421 200 583 297 441 247 437 113 385 409 558 255 582 71 332 239 324 419 450 296 298 239 265 227 382 50 119 269 349 10 530 277 591 476 479 296 539 205 324 316 496 494 509 127 264 312 360 45 470 233 560 110 136 75 401 278 523 376 446 167 276 138 275 283 352 246 529 65 238 87 555 230 244 410 449 409 446 104 123 100 505 140 417 213 478 211 326 259 451 30 178 146 207 454 479 218 366 186 373 185 501 22 385 230 447 359 504 154 556 148 537
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: 435 698 225 270 230 329 134 144 89 188 1 382 186 394 180 319 8 191 134 254 34 333 270 330 296 310 21 299 270 371 111 165 238 364 43 97 64 105 14 374 121 399 93 340 20 103 156 404 123 299 47 210 206 207 252 264 60 207 170 282 352 355 81 149 254 422 340 373 27 278 158 302 245 374 15 280 275 351 184 223 94 305 102 351 131 405 9 362 196 429 210 431 21 82 103 124 359 371 147 399 290 405 66 365 222 398 135 327 204 370 280 284 58 178 420 424 3 269 107 403 99 104 178 432 46 253 67 178 267 362 54 399 74 398 212 276 299 386 55 333 289 390 295 403 49 199 93 361 59 79 103 121 82 394 167 380 59 345 300 356 32 404 362 406 15 357 24 378 253 401 66 73 65 203 48 259 193 397 380 412 13 39 310 367 33 185 55 404 104 187 149 323 175 375 195 409 3 380 251 300 140 280 158 164 9 308 200 375 310 393 326 341 233 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 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: 611 652 87 418 245 466 29 324 421 529 152 473 31 193 104 466 69 77 270 275 117 463 375 479 3 57 237 352 52 424 205 545 505 596 22 487 321 511 54 431 121 296 82 405 295 415 160 520 201 298 600 602 306 581 338 532 268 315 407 524 156 392 248 402 464 585 275 606 331 429 145 238 136 176 468 555 234 496 166 609 93 552 6 588 365 461 325 545 133 493 34 107 327 400 48 445 217 470 415 545 399 532 375 583 223 226 133 371 329 490 510 562 367 392 171 508 247 579 94 603 370 598 263 575 132 236 264 363 315 388 271 414 46 520 453 492 192 461 146 329 87 366 127 379 150 271 157 324 285 423 354 481 73 166 315 476 417 572 91 456 277 558 312 524 439 530 100 287 64 511 152 380 34 218 119 503 428 550 350 418 264 386 2 168 7 193 215 318 228 462 92 161 119 457 233 485 244 528 193 568 426 585 69 302 27 180 223 312…
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 <= 944; 0 <= m <= 944.

Loading...
Test Cases:No test cases
No test cases available.
Ysolde and the Brass canals - MEDIUM Coding Problem | CodeTikki