CT36796

Mason's bridges Reckoning

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Mason inherited the print shop at the willow walks of Reedmarsh along with its curious bookkeeping system for bridges. Time to make sense of it. 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 <= 3554; 0 <= m <= 3554.

Example 1:

Input: 1937 2061 124 721 1124 1378 26 230 1241 1363 363 1386 135 1261 819 1260 424 1098 1244 1698 238 1190 140 1031 158 444 574 990 1077 1136 1099 1548 914 930 1111 1602 967 1049 80 600 767 775 379 1133 29 137 588 1396 584 1042 771 1897 597 1199 311 411 1829 1850 1081 1584 1348 1407 618 1129 1530 1901 427 1091 238 746 1458 1867 1132 1717 1071 1692 273 1097 1038 1295 1103 1843 232 1076 394 1552 1625 1838 331 1632 567 1285 345 657 419 459 108 670 1259 1638 617 846 157 1467 977 1104 860 909 516 1536 1273 1347 376 1269 371 376 373 609 882 1294 1194 1718 1396 1505 840 1351 355 740 962 1746 119 1830 204 1449 452 945 1315 1842 871 1742 1097 1930 306 477 1803 1929 97 1716 848 1103 1425 1565 1286 1712 720 1164 662 1270 652 1766 247 1202 1243 1770 991 1397 162 1877 995 1536 683 1787 684 1627 53 746 381 154…
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: 2567 1741 882 1324 956 1655 185 1934 609 2337 630 859 717 971 2227 2289 610 1460 1965 2548 966 1366 642 1691 506 1825 194 1902 387 1574 1133 2199 237 443 206 1747 119 2326 1256 2255 992 1379 1193 2380 524 715 2043 2149 852 1755 333 2026 1838 2114 2196 2276 411 1532 910 2369 899 1234 1509 2245 430 1350 1099 2051 42 517 130 2301 303 1559 762 1158 1409 2143 225 1055 15 917 705 1240 393 1949 1454 1935 1705 2197 719 1084 692 2190 96 1396 1412 1538 2059 2207 2348 2355 1752 2567 2183 2200 927 1678 50 1507 900 1595 16 1839 1672 1954 917 1401 838 2233 37 2237 1728 2139 1341 2421 1174 1717 1275 1837 705 1080 1107 2303 585 1674 1872 1876 1959 2289 201 389 1250 1715 329 1908 930 1892 433 893 178 720 1575 2466 1820 2413 9 2092 713 2100 1126 1294 225 298 1438 2384 889 1908 1082 1468 802 1006 431 1780 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 …

Example 3:

Input: 3330 2372 336 3116 1573 2625 500 2917 702 1312 821 2763 578 995 2031 2688 391 3160 849 1408 732 1035 107 2086 2863 2915 382 2034 1398 2007 1117 2703 2384 2828 1056 2448 1680 2317 1039 1449 658 2873 1934 3055 821 1080 734 1385 908 1931 683 2540 139 3138 455 873 513 2082 2439 3223 1243 1545 168 2560 1705 2408 1213 1963 1320 2720 304 874 2386 3062 753 2796 2281 3289 251 1294 1401 1530 2305 2907 2846 2977 1344 1708 919 939 1438 2278 2111 2484 1035 2094 2015 2882 904 2987 1205 2101 1964 2163 442 2155 106 1945 294 1950 45 2147 1231 1432 360 1877 1449 2073 406 2624 97 2554 423 2503 1847 2281 873 1132 146 553 2703 2955 950 2928 753 3295 757 1895 2312 2505 35 2754 221 2278 1863 2063 132 3166 2421 3156 1070 2941 196 589 2556 2716 774 2168 951 1901 883 2431 218 3010 1672 3321 113 1781 39 1065 519 714…
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 <= 3554; 0 <= m <= 3554.

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