CT60957

Last corridors of Shepherd

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

The council of the temple city of Sunspire pays by the answer, and Shepherd intends to earn it. First: the full register of corridors. 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 <= 2793; 0 <= m <= 2793.

Example 1:

Input: 304 109 30 217 151 250 258 283 3 257 114 215 7 39 70 257 30 82 101 221 107 128 270 289 29 239 136 217 167 268 61 286 159 182 241 242 98 135 8 41 4 27 237 260 177 299 63 144 229 285 12 152 77 126 146 285 64 237 133 201 117 240 4 277 69 281 23 142 5 158 63 124 47 255 93 161 6 294 111 158 40 236 209 237 66 233 66 93 53 287 11 74 118 286 77 112 57 225 158 194 61 172 156 158 42 118 22 226 38 146 89 190 39 129 184 227 226 243 3 77 32 248 146 197 40 239 75 97 77 182 64 133 229 247 55 302 126 195 96 113 10 53 96 297 14 156 274 275 102 283 59 178 180 295 146 178 147 299 110 246 180 282 17 160 155 204 169 293 49 78 118 160 138 205 42 192 124 268 12 119 233 234 183 288 86 115 173 191 173 188 86 295 93 233 159 239 6 272 115 195 35 142 254 303 41 154 67 266 151 235 11 14 199 233 82 213 32 186 167 170
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: 1859 73 566 716 1522 1780 111 608 1158 1691 170 1547 149 432 687 1825 532 551 574 890 1386 1405 1014 1312 757 1159 308 943 375 629 1542 1676 563 758 1190 1843 388 1322 1032 1337 1188 1636 250 700 368 1245 24 238 663 1784 944 972 627 883 572 1400 670 1150 55 1734 282 1273 53 494 1341 1369 872 1105 587 604 1258 1590 1295 1549 119 1375 518 1737 25 424 592 948 1049 1591 585 1740 840 1836 30 915 1809 1859 407 1750 918 1071 429 1571 1229 1441 1100 1407 409 1199 682 1248 294 955 47 1198 38 874 878 1338 199 661 1372 1589 1017 1843 94 660 271 589 497 741 1465 1800 10 1569 543 1634 745 872 1652 1783 103 204 1561 1841 1094 1220 201 389 595 1243 479 570
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: 2603 2094 1058 1953 1460 2281 1820 2163 65 1592 587 1725 620 2266 1681 1809 1129 1161 729 2348 1416 2219 1392 1617 1322 2274 94 1394 527 2034 70 1015 1241 2125 2181 2285 748 1232 513 2388 1327 1788 1279 2078 255 802 110 296 647 1791 638 1855 2133 2136 158 169 1515 1734 41 764 591 2263 423 1953 2007 2353 43 520 1787 2418 1502 2095 881 2478 434 1453 29 2063 762 2283 156 863 1189 1516 625 2382 144 2539 1308 2389 1700 2359 1234 1314 170 1350 713 1153 1384 2428 1016 1995 426 2343 740 1468 42 223 1510 2054 615 1831 1793 2088 241 2417 603 2013 883 2389 57 1783 1729 2274 1429 2047 236 1621 1150 1851 1308 1524 851 1241 2016 2392 185 2261 1816 2514 319 1739 1663 2065 1036 2547 137 1433 1397 2283 335 1873 2005 2363 300 2120 998 2159 233 517 392 2519 242 664 948 1644 328 2329 681 1082 633 1678 119 118…
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 <= 2793; 0 <= m <= 2793.

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