CT53669

The Saffron Build Order

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

In the heron rookery of Longlegs, Qadir the factor keeps careful count of the roads. Track down a clerical error, every figure matters. 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 <= 2887; 0 <= m <= 2887.

Example 1:

Input: 2290 460 283 941 445 479 435 2183 1110 1513 441 1567 195 1851 1455 1516 363 1738 88 873 1294 1310 1261 1347 782 1182 704 1681 148 1702 897 1002 365 640 397 1894 62 867 1389 1606 450 1179 847 1775 217 412 295 2135 1485 1636 14 148 1019 2143 246 2225 158 2105 417 965 900 2113 443 1487 496 1711 1794 2223 232 814 165 1534 1835 2097 1846 2141 187 292 1546 1912 759 1598 305 1925 53 2193 174 2271 50 1663 1226 2173 240 1141 261 1396 2234 2237 492 1636 418 1320 515 1794 937 1598 491 1707 2076 2236 670 1954 772 1431 1989 2149 1618 2172 582 1711 1767 2029 399 1822 657 2076 87 1131 1158 1824 118 1825 1145 1310 184 1467 515 1460 873 2143 988 1261 960 1212 1591 2281 927 2284 519 708 1943 2030 726 1013 1167 1978 73 1166 759 1959 1815 1922 111 656 3 2276 889 1768 93 715 1220 2104 802 1487 231 789 424 1199…
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: 1170 2619 1014 1071 580 1007 704 920 626 872 901 1040 267 1039 91 470 436 524 520 953 44 789 775 944 538 947 759 913 303 708 243 326 430 588 534 732 859 973 319 390 128 324 532 694 383 510 707 1025 684 761 780 1069 268 365 490 1027 425 643 227 586 174 921 48 1030 171 1057 537 1073 838 999 104 203 690 723 580 1033 294 859 883 1147 149 605 422 1135 279 540 813 1075 19 158 494 743 321 383 728 784 887 954 10 827 210 923 58 831 770 1094 757 853 493 510 406 1142 128 1094 743 1141 539 1081 395 820 191 948 99 231 825 980 77 663 198 606 875 1125 471 784 777 977 380 1145 126 283 479 959 508 629 98 923 404 678 174 949 5 74 9 872 105 1058 236 1114 94 1080 451 682 911 1118 36 1061 171 322 415 896 215 928 272 1080 430 591 232 326 1021 1151 9 644 405 586 538 614 556 611 583 865 460 1169 185 256 465 528 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: 1070 2803 427 499 115 119 244 252 210 689 203 948 341 357 25 327 196 859 748 921 286 674 9 1020 436 647 438 666 537 757 280 938 815 893 314 761 558 720 202 1034 680 836 42 423 380 1027 577 749 63 535 138 890 154 408 754 1061 120 425 442 709 13 64 456 794 698 909 126 956 540 941 683 986 114 951 460 491 490 1057 17 916 111 546 542 931 516 590 543 744 874 1043 87 710 238 519 272 857 619 640 48 294 168 465 360 729 689 1025 326 1051 98 1063 198 525 84 1008 348 716 816 888 876 1060 371 1004 182 544 286 534 221 242 296 683 250 987 301 1069 50 948 604 658 29 775 289 733 630 917 928 948 44 125 172 760 999 1004 187 490 11 1032 745 982 242 718 146 703 529 545 225 450 212 228 222 862 89 245 804 932 449 583 98 447 17 92 275 992 346 782 186 560 759 912 547 1057 299 545 173 413 983 997 490 1017 414 663 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 <= 2887; 0 <= m <= 2887.

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