CT60003

The Build Order of the Lunar bridges

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Every season at the cliffside roost of Stormrest, someone must decode the foreman's shorthand notes. This year the task falls to Quin, armed only with the bridges register. 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 <= 1848; 0 <= m <= 1848.

Example 1:

Input: 377 1243 237 304 157 220 196 303 167 281 71 234 19 360 12 125 17 213 102 181 197 253 179 265 334 350 17 180 48 352 28 104 241 340 198 224 104 312 137 200 200 284 103 229 11 111 60 192 128 293 223 350 175 355 278 296 46 206 248 331 161 292 83 299 134 342 179 261 39 224 91 274 45 78 104 224 251 277 57 319 7 42 92 300 194 301 23 212 157 312 224 236 197 242 184 316 47 203 162 370 78 306 48 300 189 371 116 137 231 354 156 278 95 148 87 319 190 296 38 138 157 168 333 362 180 215 5 226 40 62 42 369 15 301 136 237 68 82 156 172 18 69 43 276 298 311 308 375 5 353 280 366 42 77 17 265 263 357 344 355 11 175 91 210 112 315 208 373 6 297 169 377 4 30 91 296 154 294 119 349 8 235 145 237 281 360 70 373 72 305 116 333 187 288 6 236 191 329 48 100 302 371 164 221 161 362 58 224 155 241 128 314 67 288 8 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 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: 598 182 35 285 268 533 407 495 238 541 182 184 57 550 416 552 7 565 461 544 286 360 392 494 316 386 55 218 199 282 326 457 178 369 67 415 129 513 235 543 140 349 383 477 402 560 181 339 264 351 130 382 342 595 41 172 509 573 8 553 315 390 35 362 60 112 354 537 3 540 6 111 450 482 216 559 442 526 120 550 200 590 185 291 208 575 83 474 325 564 334 398 178 261 261 423 42 68 129 293 173 308 335 361 143 219 88 152 70 531 25 99 221 546 469 514 99 503 140 426 107 462 107 219 42 73 269 418 325 428 185 469 37 159 385 500 48 337 117 262 100 180 256 336 110 254 472 569 113 320 487 527 23 109 239 589 55 417 323 355 254 465 2 106 47 301 271 317 140 143 146 185 368 375 293 413 196 221 35 114 26 112 435 505 445 460 257 520 101 282 134 515 30 492 242 548 236 582 396 559 136 365 66 377 1 185 27 268 447 506…
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: 596 1417 443 506 275 347 132 150 76 339 16 240 142 346 244 326 62 427 351 529 67 544 199 454 575 578 429 487 160 255 290 569 325 554 25 35 226 460 153 546 125 177 261 265 146 505 465 500 21 49 256 421 24 579 197 323 39 551 133 134 60 379 85 349 365 583 513 540 317 552 285 569 259 429 147 470 65 249 17 580 409 459 25 285 217 273 7 575 169 338 224 391 278 593 357 596 243 594 25 82 13 92 277 508 123 126 266 525 54 185 68 311 139 574 160 329 127 177 107 171 11 534 104 545 79 386 328 540 69 241 219 553 255 268 281 521 304 515 124 593 47 155 314 570 37 384 41 351 162 327 407 541 394 410 239 370 240 416 183 437 175 204 167 173 10 346 158 162 302 308 515 594 56 212 232 476 16 526 5 215 18 544 332 390 5 287 50 459 161 513 307 440 194 565 59 240 192 579 331 409 9 26 106 585 3 357 25 452 253 395 38 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 <= 1848; 0 <= m <= 1848.

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