CT41175

The Build Order of Tuskmore

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

At the boar woods of Tuskmore, Mira records each roads in a worn leather ledger. The guild wants answers, not guesses. 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 <= 2336; 0 <= m <= 2336.

Example 1:

Input: 1412 1355 272 1342 400 543 681 839 257 1076 378 1072 844 1306 143 1184 411 1233 1114 1241 500 998 372 1010 392 1108 1180 1381 621 1313 769 1296 765 785 394 491 638 1341 155 1338 347 1069 374 1315 319 1326 758 1296 228 868 99 1007 548 1170 142 1299 801 1334 833 1366 373 737 391 1364 709 759 194 1048 96 717 464 964 392 1328 111 721 149 1318 483 1400 1073 1332 387 1099 731 1144 260 466 112 777 99 1190 75 553 117 1269 269 890 439 1277 777 1142 92 1273 1012 1104 669 922 805 1272 382 759 198 527 650 1172 963 1064 283 1314 278 618 345 1025 395 1268 395 1208 456 1401 54 630 328 871 944 1048 826 834 1203 1253 16 1204 294 311 12 922 147 880 316 949 194 526 224 642 246 1346 717 757 759 946 1139 1364 31 387 916 1047 295 473 759 920 1304 1354 397 886 623 1335 157 796 406 485 312 321 293 752 285 606 891…
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: 1445 87 503 1075 604 1383 231 435 760 1364 61 1424 522 596 59 756 96 923 1005 1022 91 369 66 246 519 1279 1173 1436 173 1422 677 743 8 494 186 506 818 861 1283 1306 1356 1381 204 341 123 935 82 928 603 762 369 985 673 732 50 103 526 974 388 863 868 1004 516 561 321 1413 1076 1293 567 1071 810 1173 301 1155 116 705 272 420 1229 1319 97 581 546 1003 287 387 823 1336 629 1320 418 1323 345 1407 635 860 387 1032 890 1240 200 595 510 1413 902 1301 360 1005 57 549 331 965 669 731 4 302 269 639 53 1153 65 584 511 1072 388 981 151 335 465 901 1363 1401 795 1102 743 1273 100 1195 1034 1443 393 1103 780 1231 204 360 88 955 97 232 326 1067 249 1395 372 1099 374 1404 872 1285 974 1380 227 1234 470 1426 465 621 490 774 384 1114 926 995 1109 1180
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: 2320 1249 803 2217 724 1990 286 1248 1440 2222 1069 1346 2214 2251 345 1164 177 569 734 2284 975 1008 772 1923 856 1890 137 1906 496 1894 497 1891 517 2054 864 1817 343 946 149 576 364 1642 509 1431 595 652 472 1180 1066 2211 126 275 62 1772 280 1489 252 1398 550 1296 171 2209 194 696 1195 1637 1585 1989 504 1410 2053 2222 163 746 1653 1693 602 1905 278 665 379 1773 1356 1599 856 889 1169 1184 544 819 718 2034 87 2053 280 1026 665 1227 1391 1902 1123 1703 498 1777 78 250 933 2177 579 768 329 2165 86 678 165 2156 1013 1484 1189 1761 1196 1448 628 1518 691 1808 43 273 736 1742 63 1327 1793 2260 1654 2058 1779 2028 798 1289 595 1078 1014 1426 716 1673 1497 2068 930 1981 436 1624 1540 2105 1306 1949 782 946 1713 1822 593 1283 231 420 554 797 468 1409 1968 2109 801 827 1553 2184 160 2143 221 13…
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 <= 2336; 0 <= m <= 2336.

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