CT40676

The Build Order Beneath Prismhaven

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Rhea found an old ledger of bridges in the aviary attic at the glass towers of Prismhaven. The margin notes pose a precise question. 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 <= 1600; 0 <= m <= 1600.

Example 1:

Input: 144 1241 48 135 49 113 10 79 42 63 38 140 77 96 8 126 94 101 52 140 45 123 79 90 112 115 44 123 22 64 28 129 101 124 109 137 4 76 24 53 67 84 10 23 35 40 55 75 107 127 12 31 20 28 39 92 116 125 53 133 15 46 25 116 36 89 62 94 89 116 18 50 40 101 47 124 89 129 23 25 41 86 3 86 7 40 47 95 4 128 60 62 30 93 1 136 72 104 67 76 24 90 9 18 60 106 112 130 35 108 24 50 19 41 84 113 2 142 95 144 20 54 8 43 53 136 98 105 44 74 95 101 60 101 128 132 20 97 67 91 66 97 5 127 110 111 101 110 17 88 16 100 29 118 8 98 72 142 20 30 78 124 64 69 89 106 19 28 83 97 2 125 65 143 41 46 29 94 16 48 11 22 17 117 55 128 10 107 2 14 26 48 88 91 59 78 20 128 47 101 32 47 77 106 66 106 80 113 5 42 41 93 55 104 122 138 35 82 21 123 36 87 17 93 48 53 15 50 10 35 24 35 28 134 23 130 28 65 97 118 5 55 89 124 117 130 74 …
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

Example 2:

Input: 1597 644 819 1040 221 511 498 656 531 1185 260 1328 47 1084 431 928 941 1411 344 1552 1437 1522 30 1178 435 1432 236 562 352 1439 538 1326 1032 1291 17 1402 624 1109 753 1038 1234 1440 423 651 86 455 240 399 278 1108 322 1248 62 1389 755 1194 135 298 622 935 35 193 146 872 1231 1548 632 1018 579 1462 212 884 436 1090 1171 1463 140 1417 477 487 965 1062 534 704 435 1018 158 724 728 845 459 1118 12 468 192 798 1108 1489 934 1141 919 963 27 49 1086 1517 420 1275 372 834 902 989 270 1101 234 857 708 1327 169 905 267 1093 978 1402 496 951 297 673 920 1261 1111 1384 339 1117 404 1148 261 1001 290 303 569 1234 1022 1567 332 1303 759 1087 190 1288 939 1595 315 413 1061 1396 1096 1229 167 1311 1078 1194 727 1125 100 1573 193 1262 575 850 863 1057 328 1309 535 1233 489 518 324 915 671 781 203 1479 1…
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: 502 1560 62 452 157 323 281 382 268 487 231 299 308 327 107 211 52 114 306 454 112 241 139 171 221 291 99 173 336 402 22 374 231 274 233 424 412 495 8 249 83 247 153 314 455 458 264 445 322 465 170 359 345 435 44 274 6 226 80 362 6 255 118 306 313 492 28 140 111 289 70 199 168 449 106 242 44 424 18 96 256 364 436 446 12 293 203 480 187 325 205 307 29 175 108 153 360 460 48 401 134 494 393 443 147 492 166 502 246 462 136 207 86 198 294 345 182 203 377 483 122 207 318 460 6 430 205 226 200 502 18 310 64 120 44 261 104 167 390 466 44 208 361 491 327 381 328 501 26 201 40 353 68 85 41 80 94 119 17 155 72 263 79 104 210 256 155 345 242 427 39 295 229 246 441 466 225 334 293 328 152 283 415 502 122 403 261 405 178 380 42 460 221 326 38 119 49 438 338 453 7 393 290 419 330 482 51 202 340 344 167 …
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 <= 1600; 0 <= m <= 1600.

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