CT58025

The Build Order at Palemere

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

At the salt flats of Palemere, Diya records each bridges 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 <= 1527; 0 <= m <= 1527.

Example 1:

Input: 102 1195 3 31 60 80 60 63 53 65 45 83 35 72 60 90 21 85 51 55 23 69 53 101 24 71 73 98 14 90 53 90 61 83 51 79 15 42 48 53 16 95 58 77 46 88 36 94 17 100 10 74 35 47 9 79 13 56 15 101 50 69 4 73 35 45 61 94 2 29 11 31 64 97 7 23 10 32 18 57 39 91 37 50 52 96 7 96 63 76 45 47 10 72 43 62 32 89 3 40 12 17 36 66 16 23 43 54 41 101 45 48 3 54 13 40 90 94 24 84 10 53 16 77 73 88 2 34 8 85 29 66 32 100 39 53 27 55 2 43 50 59 21 59 13 26 74 101 32 65 16 30 57 101 56 58 22 70 3 50 43 56 14 33 36 47 2 55 35 54 25 32 17 83 9 19 11 32 45 68 10 92 4 94 30 53 3 100 2 17 8 83 5 88 92 93 50 102 10 102 59 91 4 55 8 54 53 58 30 42 4 32 59 88 12 79 27 90 70 78 13 29 87 89 8 56 69 96 31 54 53 84 50 53 74 82 26 97 29 46 15 44 11 68 55 75 31 37 6 63 14 41 30 81 66 75 9 38 39 82 32 81 28 38 18 75 59 72 20 34 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

Example 2:

Input: 1422 855 142 563 908 1020 1121 1187 158 1346 854 1125 296 1267 616 720 835 1326 779 1044 847 938 474 966 884 1259 125 429 544 1284 673 744 378 686 252 1408 146 383 486 1151 443 606 165 903 63 154 49 1242 40 350 1181 1352 863 1345 392 1357 168 547 99 722 178 1399 724 1341 904 1004 101 803 102 1083 438 903 155 803 420 1135 327 911 84 476 930 1254 799 1099 114 1185 33 204 915 1056 174 1400 276 291 932 1138 1338 1402 94 401 884 1079 325 1291 700 810 201 418 828 991 533 1242 1249 1314 706 996 857 1228 595 1354 827 1338 259 672 295 1214 471 1399 705 1275 60 930 110 322 20 1286 990 1160 306 1268 1182 1189 432 812 342 1061 600 1073 132 1079 27 1139 142 274 235 1095 200 372 1164 1170 47 128 161 390 931 1389 323 449 787 1229 1058 1177 203 614 86 245 316 786 141 568 1083 1413 588 637 355 1378 453 119…
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: 171 870 1 144 52 150 44 77 114 153 49 127 44 109 24 62 7 156 58 155 98 101 81 131 26 78 45 86 59 162 47 127 32 86 53 66 13 72 59 72 109 122 23 171 27 165 5 164 55 170 98 170 20 71 30 38 26 49 154 166 29 50 45 78 53 142 14 141 86 122 26 158 21 60 64 142 141 171 16 28 24 131 42 137 71 93 60 170 82 96 105 141 112 159 25 86 68 71 6 61 103 160 77 159 49 52 4 168 1 33 160 163 104 111 34 110 4 124 60 86 29 87 50 141 136 157 98 163 61 131 128 149 59 149 124 125 1 132 76 96 64 126 109 121 105 116 17 162 27 103 5 52 94 102 51 134 27 132 64 65 65 120 54 67 134 155 61 95 134 147 71 81 42 82 45 104 88 121 59 164 46 65 17 164 42 123 135 170 95 138 69 138 75 92 85 104 27 78 9 79 132 146 97 152 110 112 122 133 68 94 21 82 143 155 24 106 118 126 75 89 25 136 7 169 35 159 3 31 41 169 66 94 62 119 112 117 52…
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

Constraints:

1 <= n <= 1527; 0 <= m <= 1527.

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