CT57970

The Build Order of the Silent bridges

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Morning light hits the silver mines of Lodebarrow as Arjun unrolls the day's manifest of bridges. The tally will decide the next shipment. 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 <= 1873; 0 <= m <= 1873.

Example 1:

Input: 971 1309 112 710 161 901 66 674 117 234 17 630 9 970 606 735 417 455 808 928 411 613 227 478 139 240 802 859 684 961 841 853 287 958 691 850 220 473 142 705 80 759 177 680 235 579 320 464 275 667 291 292 450 731 732 835 305 350 7 847 134 462 668 848 54 881 207 545 277 545 365 398 359 815 242 600 290 868 265 831 184 743 461 464 675 909 28 190 309 622 253 298 141 930 122 896 313 588 526 803 529 699 249 545 66 965 242 815 405 721 90 299 152 892 278 621 134 805 137 551 122 367 595 831 99 961 173 714 32 791 42 633 42 628 813 840 296 890 31 183 945 969 618 732 476 556 61 306 529 671 139 529 283 514 530 586 279 283 74 273 458 469 639 697 152 192 218 322 624 639 198 812 109 472 666 951 419 583 597 937 223 957 519 701 263 633 95 543 348 699 86 519 203 646 327 815 35 576 297 814 442 795 173 489 87 9…
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: 157 561 82 89 43 84 4 121 67 111 34 123 107 155 85 92 27 90 57 111 2 93 29 89 104 105 52 145 110 157 33 36 80 82 35 72 34 104 53 87 7 89 12 54 84 144 33 52 116 118 6 43 44 138 45 49 109 111 87 90 71 138 32 56 87 143 56 89 8 25 92 156 82 122 109 122 41 58 38 87 69 117 83 119 43 82 56 103 103 108 102 124 118 154 41 97 6 149 31 41 30 54 34 156 78 129 5 18 33 60 24 46 10 36 69 149 16 155 12 40 90 103 29 88 78 157 2 91 99 143 37 38 68 156 100 156 88 103 54 55 126 149 69 79 46 129 36 95 5 133 43 111 11 30 60 95 96 125 125 143 6 42 22 91 13 101 100 106 27 125 85 123 6 46 5 125 122 151 29 113 85 144 101 135 67 117 49 118 10 45 120 125 34 83 59 85 26 64 73 146 37 146 10 70 34 105 108 121 72 108 63 120 53 95 87 109 5 45 31 48 29 152 16 100 82 121 39 47 40 121 21 101 20 122 51 124 77 140 14 56 93 114…
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

Example 3:

Input: 1051 1096 57 598 796 904 129 704 325 578 81 381 503 572 162 480 157 838 134 270 53 945 582 828 311 514 517 541 248 825 622 657 453 979 562 849 447 480 291 823 85 884 381 427 372 907 251 814 19 512 43 338 480 730 288 837 396 491 443 738 369 917 384 1049 556 976 209 578 918 924 388 866 201 326 629 673 487 1005 58 209 550 729 108 488 47 801 5 136 876 934 509 968 342 779 111 332 267 476 321 465 51 365 271 1048 514 947 130 917 411 591 586 725 153 201 310 402 51 795 796 802 196 884 342 852 655 894 38 970 743 994 518 550 526 946 424 939 239 315 123 342 249 737 256 362 233 819 568 962 105 541 668 882 140 947 331 924 183 798 27 59 796 836 202 645 445 944 282 902 732 981 13 476 67 568 697 742 115 176 148 251 238 656 528 906 48 1051 152 719 50 235 396 494 195 360 873 897 327 483 124 190 3 913 258 787…
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 <= 1873; 0 <= m <= 1873.

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