CT46853

The Celestial bridges of Tarun

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Tarun the store warden watches over the fox den of Rustwood's stores of bridges. A careful computation stands between order and chaos. 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 <= 1110; 0 <= m <= 1110.

Example 1:

Input: 985 819 35 526 375 645 284 427 55 312 550 917 44 123 305 840 176 575 354 983 163 475 258 735 31 502 294 422 510 972 926 978 307 340 414 816 280 631 458 501 110 906 519 527 662 742 569 861 277 735 497 868 394 437 588 828 459 749 276 579 222 617 442 676 670 675 229 923 390 813 327 483 123 502 184 491 782 827 149 229 310 937 793 820 202 704 408 482 551 976 387 963 513 545 250 349 335 360 328 631 359 557 166 917 147 465 41 118 255 918 8 73 188 689 214 888 550 617 402 674 185 335 440 533 482 976 155 177 480 628 594 718 701 834 20 833 52 915 78 840 123 498 9 477 315 598 41 149 39 519 570 793 93 313 20 487 10 57 309 604 651 899 214 521 110 198 206 974 649 958 161 337 447 747 574 663 24 765 260 849 53 543 841 953 412 851 1 620 163 255 625 760 108 948 167 364 160 468 117 911 610 781 231 249 369 930…
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: 763 977 66 582 162 251 302 415 256 462 502 627 150 542 105 365 191 577 88 438 51 532 113 492 457 657 351 478 150 396 378 675 10 671 100 266 321 572 53 565 63 175 435 531 131 556 51 687 228 326 488 595 312 340 307 337 424 721 283 749 511 534 540 664 73 590 695 735 284 292 452 761 126 421 62 642 361 677 26 691 147 282 511 596 543 738 422 743 275 711 490 760 203 738 39 616 333 363 161 562 77 617 359 392 151 155 321 725 217 535 540 697 323 705 458 584 241 691 560 637 45 531 133 485 183 586 715 763 460 490 401 414 236 746 381 752 323 620 467 589 241 264 33 122 14 18 464 655 443 517 565 677 368 518 625 658 352 763 25 412 544 669 411 638 30 630 396 558 418 687 584 652 17 226 184 620 263 317 369 575 572 610 259 630 194 281 36 235 436 640 564 631 16 657 5 521 148 337 427 467 51 674 589 741 29 204 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 3:

Input: 85 735 6 33 5 80 22 51 14 16 11 58 20 43 42 81 37 75 3 29 12 13 48 54 24 73 36 53 33 63 4 53 9 77 32 77 36 80 2 10 25 34 56 81 32 56 57 78 40 59 11 18 53 56 25 27 1 8 42 75 1 13 19 62 37 48 15 69 48 53 30 59 6 51 16 27 64 85 1 82 13 21 22 50 51 78 9 71 15 23 12 54 63 66 12 65 16 44 28 76 37 71 6 34 51 77 46 51 17 72 43 80 20 51 10 22 19 50 43 68 1 57 35 73 62 76 25 30 11 28 3 48 70 73 46 64 5 66 23 27 4 11 54 77 12 39 55 60 18 42 18 23 8 43 16 41 39 41 43 83 59 83 9 37 34 53 48 66 43 64 15 71 31 72 35 44 22 70 8 83 20 44 37 50 15 47 17 58 30 52 7 75 51 65 12 52 60 73 28 39 31 40 39 45 50 73 38 83 10 37 5 39 19 63 11 57 12 79 35 85 24 80 22 47 41 85 26 35 6 7 44 45 24 30 41 69 47 67 72 78 32 62 13 30 41 67 46 80 45 46 23 82 36 72 17 52 15 34 1 53 9 43 19 42 40 46 30 77 15 21 20 37 3 28 25 7…
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

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The Celestial bridges of Tarun - MEDIUM Coding Problem | CodeTikki