CT59962

Lara and the Amber bridges

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Legend says the vault under the crane marshes of Stillwater opens only for a perfect tally of bridges. Lara 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 <= 870; 0 <= m <= 870.

Example 1:

Input: 242 100 68 242 129 222 192 205 22 181 96 134 47 71 49 222 75 148 224 235 55 139 20 185 33 166 106 179 45 66 105 212 105 129 11 236 64 109 88 180 6 172 191 241 75 198 36 39 38 213 27 49 46 68 70 146 7 168 138 201 176 208 158 225 75 78 185 230 83 151 27 223 107 113 109 110 121 190 32 207 32 159 106 238 38 220 87 188 109 220 56 213 23 175 20 191 72 103 53 119 57 166 48 76 123 207 24 104 40 202 103 207 220 231 32 54 35 72 84 90 112 208 23 135 32 179 162 204 75 185 66 159 20 197 95 217 93 184 126 148 138 151 148 164 205 211 56 79 102 232 3 209 146 216 155 158 184 238 189 236 116 224 88 136 140 181 30 215 57 133 133 161 85 88 70 137 72 145 74 174 61 180 122 174 26 215 73 233 74 158 93 153 114 209 48 161 192 228 136 148 168 174
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: 613 482 355 568 206 482 88 529 183 545 135 612 143 440 160 272 242 382 225 340 534 561 428 567 284 323 227 472 196 591 448 485 231 517 155 379 129 192 131 394 60 111 148 492 143 215 10 613 220 595 63 430 186 430 82 438 290 371 172 241 34 136 195 423 157 472 37 469 428 473 275 304 90 164 5 415 35 92 506 556 186 513 506 540 74 282 164 308 202 226 257 540 67 228 139 166 157 167 434 450 273 568 18 185 362 455 83 342 583 598 314 455 395 598 18 223 152 197 146 211 39 569 485 496 19 136 85 168 192 345 201 612 231 488 459 591 499 548 304 532 154 548 35 431 242 299 227 229 38 100 208 364 329 436 272 294 13 480 40 357 202 473 332 364 195 577 379 438 320 588 151 271 48 151 88 349 387 573 178 355 131 495 315 515 71 105 196 465 550 589 101 211 46 585 317 505 34 152 47 462 81 308 105 288 27 407 82 149 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 …

Example 3:

Input: 810 253 134 675 372 490 210 594 138 761 719 724 359 494 237 255 369 755 302 686 423 677 47 323 486 508 195 551 372 501 144 619 541 549 259 646 344 392 80 520 165 242 178 803 135 607 577 601 600 805 290 581 200 224 243 781 56 722 128 569 542 584 513 601 262 426 252 627 157 273 136 747 328 658 202 249 167 676 43 338 412 604 254 782 5 334 33 216 29 646 406 473 272 442 423 490 113 399 235 798 177 699 624 626 218 532 9 742 48 609 21 670 210 717 494 741 197 494 512 538 237 595 60 443 98 716 602 729 271 756 300 514 266 676 64 149 404 709 416 806 37 644 281 492 329 330 49 531 649 773 351 566 435 579 315 762 241 284 283 517 317 537 151 584 669 766 226 282 188 579 154 602 49 122 35 754 108 671 73 105 132 735 323 374 390 411 592 732 231 496 469 720 668 706 430 627 659 712 339 406 453 802 412 701 445 …
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 <= 870; 0 <= m <= 870.

Loading...
Test Cases:No test cases
No test cases available.
Lara and the Amber bridges - MEDIUM Coding Problem | CodeTikki