CT59171

The bridges Build Order Puzzle

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Deep in the fox den of Rustwood, Kian 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 <= 2039; 0 <= m <= 2039.

Example 1:

Input: 1793 1721 130 1116 1538 1604 184 1026 957 1295 581 898 1245 1778 866 1083 1003 1504 874 1459 978 1462 795 1697 1418 1674 1138 1353 423 886 237 902 346 516 1279 1286 1293 1551 144 1755 816 1721 355 1739 230 1604 989 1414 11 1480 100 273 143 952 997 1174 368 1765 461 1148 136 787 493 1041 557 1014 595 965 302 399 82 1675 578 1487 309 855 8 988 998 1350 150 954 208 1716 467 889 412 790 771 1734 1109 1369 72 208 404 1466 382 744 138 446 10 178 513 1576 760 1443 1344 1777 543 1037 1376 1643 862 893 807 1320 129 1620 669 836 611 1655 982 1730 679 1317 1046 1493 352 420 597 720 599 619 811 1600 30 1006 218 443 477 948 122 1448 103 984 46 86 876 1207 447 1618 472 675 92 880 206 719 504 1057 69 124 739 1189 275 1777 302 1681 78 1058 917 1389 910 1621 148 183 516 988 204 608 1139 1191 993 1189 111 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 2:

Input: 482 56 279 412 294 378 99 406 124 273 430 472 49 417 78 264 36 422 117 183 1 297 87 200 309 480 194 425 59 117 204 321 259 345 44 353 82 313 243 393 53 450 73 174 66 273 459 468 247 383 383 446 301 401 25 411 291 326 68 350 3 337 58 301 54 338 40 71 56 241 201 473 321 377 216 287 75 99 49 235 224 244 148 433 223 463 152 325 2 412 112 275 83 136 26 364 256 442 94 362 167 177 120 361 335 362 98 410 201 428 280 375 226 263
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: 688 1483 31 506 590 591 97 142 604 637 130 387 13 93 374 540 248 432 268 316 31 455 565 622 192 656 243 495 483 581 513 525 288 466 136 402 503 687 530 600 393 394 61 65 526 540 34 685 107 428 99 217 74 182 231 599 439 481 7 378 48 629 110 227 63 132 83 479 560 624 3 684 220 663 368 657 400 626 306 329 67 257 251 594 255 624 105 532 408 626 161 195 136 507 286 662 64 508 232 665 123 458 136 480 534 678 622 653 388 671 120 433 461 598 362 468 37 430 395 649 464 602 39 232 119 163 99 264 35 442 250 303 278 324 144 486 174 464 452 558 99 514 249 261 354 497 173 180 351 389 82 651 10 684 184 580 152 384 264 304 110 296 264 408 614 672 380 504 244 364 536 604 612 681 180 664 353 485 171 677 389 474 4 510 198 582 195 487 63 546 101 608 295 501 51 656 5 654 22 686 411 436 47 233 195 231 322 328 5…
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 <= 2039; 0 <= m <= 2039.

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