CT59284

Petr's Ledger of bridges

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Deep in the orchid house of Bloomglass, Petr 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 <= 1250; 0 <= m <= 1250.

Example 1:

Input: 687 433 411 487 307 626 397 424 69 456 62 122 9 664 449 594 120 273 69 197 163 498 168 179 239 333 79 602 450 639 57 393 178 480 385 618 389 484 10 50 73 408 90 669 114 295 172 581 314 676 439 446 164 182 238 646 439 630 292 395 120 238 250 656 11 254 286 447 357 428 72 375 243 403 154 260 265 575 240 252 119 184 120 414 228 251 264 477 12 213 142 619 38 152 502 653 210 504 24 315 193 363 433 528 172 216 234 665 59 124 376 484 77 671 566 623 196 564 320 338 31 624 216 443 10 14 393 622 175 448 2 309 178 217 315 682 216 300 175 433 211 300 276 652 462 680 398 535 11 351 421 645 528 539 443 539 163 568 120 275 317 619 24 377 516 531 507 580 249 685 293 563 326 405 146 405 219 303 220 466 152 158 649 658 259 676 262 296 299 606 191 357 153 404 122 481 297 648 144 364 312 633 48 406 143 261 18…
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: 1221 463 622 747 943 1037 820 914 157 281 189 1133 592 1092 912 984 957 1090 17 1195 18 1129 545 1190 345 1035 734 1037 150 169 33 473 254 428 381 1099 144 246 914 1107 511 561 717 1101 919 1119 71 686 392 611 496 556 642 1040 282 572 871 888 183 1025 93 440 19 431 93 1212 13 349 207 718 389 1205 142 580 343 686 57 1137 874 1203 48 1156 480 1135 293 324 729 1198 11 968 67 767 67 774 131 1166 761 1111 525 1097 890 1116 412 594 190 538 287 1020 236 553 33 1206 187 949 74 1171 159 1183 157 722 899 902 15 259 29 166 62 409 161 920 850 956 675 1103 448 635 514 619 245 445 39 305 725 826 378 494 59 404 22 582 140 552 589 1138 287 460 253 427 895 1011 313 937 27 252 545 1013 224 229 461 523 111 1149 242 1025 264 394 774 1093 126 986 552 862 302 887 225 944 786 1153 87 1214 582 871 426 642 23 602 …
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: 856 218 322 401 671 745 12 592 361 587 692 700 388 475 57 543 35 658 151 841 804 811 273 399 247 587 619 630 339 744 271 786 238 405 289 315 454 806 3 772 336 629 273 670 297 745 738 799 136 383 110 582 43 796 438 724 90 132 558 743 217 798 136 163 384 480 233 266 233 617 193 237 220 618 693 745 469 785 495 732 315 383 507 615 320 804 17 218 350 376 352 723 193 665 116 461 212 433 360 474 153 603 6 612 356 434 615 817 136 645 471 835 40 279 459 671 555 843 555 686 340 810 202 668 27 788 137 701 183 547 328 530 42 110 522 631 279 701 112 637 146 708 29 791 550 828 542 692 395 851 243 603 489 671 483 717 642 781 309 816 437 480 623 855 320 359 393 450 33 564 192 580 518 812 519 715 411 426 336 813 456 461 584 649 370 749 497 507 170 499 739 742 248 380 381 469 410 659 195 462 526 580 68 507 …
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 <= 1250; 0 <= m <= 1250.

Loading...
Test Cases:No test cases
No test cases available.
Petr's Ledger of bridges - MEDIUM Coding Problem | CodeTikki