CT51130

The Build Order of the Umber routes

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Seth runs the aviary at the quartz ridge of Glimmerfell. Today the books show a list of routes, and the numbers must be worked out before sundown. 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 <= 3349; 0 <= m <= 3349.

Example 1:

Input: 1777 1000 56 818 756 1003 123 230 672 1704 439 647 693 1162 1197 1325 1026 1182 283 1109 1484 1567 702 917 725 1110 95 954 38 1384 1229 1285 328 975 881 1088 738 1305 489 752 944 974 235 267 533 1342 67 486 748 1033 979 1490 399 907 1210 1546 378 852 322 1501 409 457 1232 1586 245 496 94 379 131 186 355 384 979 1524 332 887 24 1680 420 1761 15 1456 1300 1381 473 1208 1136 1271 1315 1486 775 940 951 1245 1316 1659 865 1030 239 633 276 1667 254 792 382 874 932 1240 113 845 562 607 285 1235 33 924 970 1546 699 1647 156 296 223 1584 392 575 1183 1685 198 1491 445 1674 131 1608 172 494 1545 1677 910 1108 661 1073 602 723 323 917 315 1149 389 1199 1166 1656 650 994 907 1532 79 384 1035 1658 423 767 721 946 1214 1578 166 1237 42 1291 667 719 484 1408 1070 1727 302 779 296 1006 832 1445 713 785 75…
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: 2176 2216 703 873 256 1613 558 1947 1612 1837 1057 1588 945 1085 518 2058 92 1302 605 1043 1121 1963 95 1873 960 1708 109 1054 451 1859 1258 1525 63 1594 582 1194 592 1481 635 1862 795 1028 90 865 953 1474 1506 1762 517 1152 1 1868 596 1481 810 2071 895 1558 68 671 479 1757 140 2078 132 410 934 1205 224 2108 921 968 311 1612 1802 2126 1291 1583 615 1849 1502 2054 1327 1979 313 1676 324 899 2007 2117 1269 1802 1311 1616 522 919 469 1343 430 1744 804 1810 1791 2106 998 1633 1775 1842 5 1701 1257 1452 1659 1984 495 967 1255 1469 1622 1950 1113 1491 1548 1868 132 1813 1379 1710 623 837 900 1007 1062 1521 1528 1760 28 2114 1568 1993 112 993 288 1263 313 1158 453 723 694 2170 1052 1580 357 806 978 2120 177 1845 230 1463 268 346 638 1974 299 812 795 1347 355 622 518 1843 247 1204 1433 1844 1636 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: 2219 3250 1199 1322 156 2175 213 1119 615 1890 1191 1394 470 1169 78 881 372 1320 2100 2211 1854 1996 751 2125 276 2114 985 2151 812 902 251 380 1164 1736 1431 1476 94 688 852 1563 789 1030 1802 2156 991 2139 515 1831 660 1234 2010 2061 1157 1337 161 1210 201 879 136 1417 1405 1461 543 1602 45 1579 714 1026 71 105 99 682 1456 2033 975 1507 1195 1820 249 435 1109 1289 863 889 299 874 193 1244 1254 1821 835 1168 1657 1995 736 1044 959 2218 328 565 1984 2205 297 1515 1011 1640 1620 1708 1164 1698 1439 1863 2019 2045 418 1368 1444 1526 759 901 171 439 1118 1562 598 979 24 83 1083 1903 701 866 1007 1828 539 2170 647 954 67 2119 250 350 960 1792 40 869 1217 1807 1043 1232 1945 2107 351 1009 84 785 1470 1487 1522 1544 435 654 6 1193 1881 1897 1674 1983 1048 1337 1636 2161 845 2115 20 154 1137 207…
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 <= 3349; 0 <= m <= 3349.

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