CT37612

The bridges Build Order Puzzle

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Every season at the otter slides of Sleekwater, someone must restore an old family record. This year the task falls to Orin, 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 <= 2308; 0 <= m <= 2308.

Example 1:

Input: 972 1158 727 887 378 690 483 619 60 228 321 343 87 208 309 841 249 369 190 768 14 129 558 665 32 143 215 928 111 460 349 820 174 271 656 926 33 601 170 775 90 344 368 450 252 435 133 155 182 590 188 195 767 880 617 870 158 239 139 802 106 859 139 716 375 410 447 590 637 866 676 815 779 929 87 394 175 495 675 691 712 935 910 936 111 302 478 629 910 947 548 897 58 441 598 661 525 545 108 240 711 967 36 901 323 783 208 706 444 786 518 776 129 223 519 925 264 962 688 815 92 256 379 881 202 434 34 103 424 681 122 442 220 931 205 419 39 861 156 212 26 503 113 564 126 924 661 758 117 621 764 803 31 88 850 897 78 553 467 638 573 672 141 153 193 392 122 127 564 597 83 169 144 344 93 585 194 564 231 281 669 927 488 781 78 82 101 501 73 444 318 344 189 344 503 709 402 549 34 502 74 589 280 655 73 778…
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: 181 2040 7 135 1 121 53 119 12 50 3 58 7 139 128 165 78 141 118 167 112 125 15 168 20 119 35 162 65 91 34 166 79 133 47 55 67 175 136 154 78 93 29 50 25 148 112 120 5 57 168 176 143 149 138 176 25 115 50 153 48 50 54 110 16 168 99 154 37 77 20 79 68 101 28 59 34 106 56 77 136 168 70 121 42 60 86 166 6 108 47 133 71 165 10 148 149 164 50 67 13 78 101 104 48 168 124 150 1 178 59 75 34 180 1 158 55 101 29 44 125 129 28 50 55 102 46 77 55 82 97 120 22 136 32 95 40 123 63 175 16 66 90 116 62 92 35 126 85 144 145 177 62 102 63 80 66 145 23 166 25 137 61 105 126 166 73 108 10 107 40 101 68 76 64 100 91 97 37 115 86 175 87 101 12 27 16 118 1 137 10 43 68 92 100 148 90 134 7 56 81 147 146 172 106 119 109 158 10 158 44 68 7 152 158 180 47 51 52 151 94 115 3 125 149 157 60 111 107 179 10 28 14 32 19 …
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

Example 3:

Input: 1701 875 1179 1445 255 618 962 1605 303 1456 407 1636 322 1278 226 1540 331 1467 29 663 83 1005 248 1457 993 1168 934 1310 1204 1654 315 455 555 1669 1 1462 434 1311 351 1493 281 336 253 1659 422 1499 154 999 21 1592 1222 1364 722 1024 411 1138 604 739 410 648 440 1384 683 1283 80 828 441 1140 1067 1103 792 1368 801 1012 514 526 793 1328 1300 1534 73 1511 946 1149 590 1135 613 878 566 1166 101 1384 1188 1579 1613 1686 46 1178 750 834 648 1187 193 1289 14 531 263 913 1062 1682 404 748 1141 1664 558 949 990 1651 1104 1378 657 1189 141 149 202 935 355 580 42 1333 105 352 450 846 1069 1599 577 1649 912 1350 992 1489 513 1198 86 524 273 569 292 378 60 376 1061 1326 62 1375 389 724 179 1276 433 1571 487 643 1417 1568 636 1435 527 1309 181 1496 678 1473 98 1064 245 948 990 1080 18 890 1073 1313 6…
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 <= 2308; 0 <= m <= 2308.

Loading...
Test Cases:No test cases
No test cases available.
The bridges Build Order Puzzle - MEDIUM Coding Problem | CodeTikki