CT45683

Wren's Build Order Ledger

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Wren inherited the depot at the silver mines of Lodebarrow along with its curious bookkeeping system for roads. 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 <= 2723; 0 <= m <= 2723.

Example 1:

Input: 2326 1438 317 862 563 1164 936 1997 1373 1672 1135 1516 563 1643 1101 1870 967 1324 1400 1684 610 862 28 270 685 1113 702 1246 262 1489 1356 1590 123 734 923 2297 658 1116 2108 2249 124 654 1729 1802 1450 1684 611 1332 674 2018 310 2236 692 1502 721 1897 545 870 1180 1537 963 1844 1376 2024 7 952 379 2292 631 951 116 1941 525 746 959 1585 169 1909 62 2045 629 2293 785 974 750 1072 245 505 796 1727 1522 2225 454 1860 1166 1392 1968 1991 815 1962 958 1802 842 1660 956 1550 2096 2133 1166 1424 556 1920 1130 1894 1182 2172 6 1439 411 2172 305 1342 1057 1429 790 2100 1181 1299 139 1702 8 1793 735 1424 715 1000 919 2178 133 1205 690 1153 2160 2312 647 1452 2009 2115 405 874 1259 2149 500 1041 480 1419 477 891 1008 1684 1211 2052 8 63 195 1936 429 1600 1310 1882 473 2291 1161 1599 411 1842 107 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 …

Example 2:

Input: 1610 927 258 1558 355 748 557 1459 135 354 653 675 354 1075 671 1572 676 1562 29 1084 875 932 385 623 376 1341 321 1378 417 1292 645 1013 355 959 234 330 81 925 829 1088 937 1424 338 1306 353 586 205 1036 802 1107 66 1224 146 1605 1337 1424 962 965 650 1353 519 645 1100 1549 872 1202 526 657 717 1439 1419 1518 306 1170 74 599 415 652 873 1002 180 705 154 1203 974 1125 210 1108 9 139 827 1586 280 725 32 508 1001 1108 1391 1395 46 89 32 1254 120 1214 220 832 733 1454 195 1210 278 541 311 1180 401 412 1244 1608 34 184 556 1005 327 383 585 1092 1087 1525 47 106 1288 1323 988 1495 884 1543 405 1056 758 1304 390 813 636 1560 227 1007 455 778 1031 1417 210 1257 103 1519 157 861 323 694 90 1138 100 992 519 1511 67 1062 682 1355 16 1275 379 1033 308 730 1229 1415 335 1000 923 1464 480 886 98 1543 3…
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: 269 1642 147 173 146 152 75 104 139 157 157 194 220 243 73 267 48 93 218 219 88 122 4 254 24 25 88 195 29 81 64 187 119 176 4 229 52 148 65 106 10 12 22 218 85 230 80 123 208 268 43 56 71 240 184 191 52 214 86 221 175 183 96 174 34 201 53 182 31 71 133 187 89 95 239 264 100 126 138 207 132 260 193 202 94 158 121 147 64 236 97 258 35 37 75 134 96 269 17 132 22 168 140 262 129 262 12 177 55 81 144 247 21 33 105 202 245 249 94 157 114 173 134 167 61 208 62 226 22 97 92 242 66 156 21 160 106 183 70 242 146 219 92 144 22 214 107 122 131 186 5 259 33 60 45 85 125 195 83 209 91 198 6 141 3 207 203 234 32 205 7 127 160 202 38 109 161 266 9 161 4 11 115 192 116 251 34 211 34 221 133 200 53 80 30 211 48 117 38 246 121 148 96 217 60 119 75 232 135 205 43 215 228 260 64 138 84 222 11 17 110 235 6 78 8…
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 <= 2723; 0 <= m <= 2723.

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