CT53212

Squire and the Bronze bridges

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Legend says the vault under the shipyard of Keelwind opens only for a perfect tally of bridges. Squire means to find out. 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 <= 3416; 0 <= m <= 3416.

Example 1:

Input: 799 704 19 231 532 636 421 456 144 287 151 517 122 154 511 793 18 83 645 772 296 690 40 235 532 604 77 243 447 738 139 502 5 313 319 541 95 249 639 687 243 767 99 335 254 722 275 542 55 404 20 398 37 384 120 406 7 525 350 577 647 668 159 634 697 703 229 424 150 482 337 357 267 686 58 298 55 345 355 465 85 774 268 556 306 723 131 526 251 344 203 566 360 407 390 755 120 240 134 278 617 633 352 763 181 755 127 414 298 629 60 168 385 780 463 517 307 367 544 794 427 448 23 223 1 675 360 496 118 233 25 796 43 200 170 212 6 758 394 767 227 515 260 494 278 714 340 527 432 597 487 660 470 484 300 503 166 391 358 393 626 692 471 669 537 589 298 482 244 637 449 786 41 613 570 672 190 769 71 770 335 767 97 631 250 788 184 691 263 614 228 424 614 758 375 665 158 563 462 796 128 302 95 363 148 517 181 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 …

Example 2:

Input: 2893 1378 1071 2259 701 2801 1601 2628 1230 2509 644 1144 2029 2792 136 459 47 2840 2576 2584 282 400 890 2235 54 80 1389 1783 819 1261 544 2703 2241 2430 671 1569 373 2388 1398 2352 1922 2442 800 1845 565 1569 1655 2296 1100 2376 1328 2401 315 2129 1207 1430 1972 2805 1510 2478 905 2091 944 2124 157 168 1535 1993 570 2043 316 953 1882 2418 779 2042 203 2314 695 2559 614 1840 1927 2189 506 911 743 1808 293 2078 481 1538 2442 2544 607 2430 603 1938 149 1267 113 1747 198 464 1604 2412 1018 1757 709 2839 951 1141 167 1538 38 1983 571 2608 876 1615 1580 1962 2282 2556 538 1915 112 273 937 1128 466 539 147 2878 180 1111 632 2039 1995 2648 289 1989 745 2009 2026 2677 79 1171 1111 1310 705 1964 1334 1484 846 1324 1192 2833 505 1197 1678 2077 1294 2538 1147 2019 1651 1842 2277 2712 1545 2625 492 2…
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: 875 3406 109 804 159 440 83 271 647 695 560 586 607 652 392 546 600 626 14 139 391 855 404 581 103 813 261 315 13 716 337 761 579 600 88 765 42 712 129 770 573 636 649 857 55 82 407 567 338 408 662 870 143 630 326 333 91 254 67 456 655 863 248 362 320 708 411 489 247 388 280 526 246 823 112 690 3 650 236 442 269 742 291 595 213 799 12 639 586 719 12 505 289 411 149 291 578 689 96 457 702 850 193 274 6 281 533 704 397 602 464 840 358 464 389 469 268 609 554 798 505 675 486 827 57 363 73 345 89 347 83 239 76 658 271 671 544 724 525 851 7 160 474 819 490 861 392 559 22 562 204 568 538 702 285 595 80 133 450 732 223 426 107 758 337 561 82 702 28 613 708 715 459 601 498 875 133 544 174 800 309 327 610 820 245 575 305 642 242 270 339 601 8 728 682 787 213 265 486 531 196 395 246 706 73 123 60 72…
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 <= 3416; 0 <= m <= 3416.

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