CT42836

The corridors Build Order Puzzle

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Morning light hits the cliffside roost of Stormrest as Tailor unrolls the day's manifest of corridors. The tally will decide the next shipment. 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 <= 1666; 0 <= m <= 1666.

Example 1:

Input: 317 406 51 152 83 293 1 180 113 279 257 280 143 267 202 312 67 194 68 240 3 54 170 178 129 194 96 240 9 195 51 236 79 140 95 165 51 202 164 183 8 218 218 274 295 308 2 136 46 63 11 147 198 237 49 259 43 228 137 312 46 155 50 286 11 188 96 127 1 288 243 252 62 182 10 147 10 297 149 227 40 130 2 111 71 106 153 301 11 77 54 305 130 211 200 262 69 115 43 110 8 225 149 197 258 264 115 291 89 284 14 18 182 257 146 223 191 229 50 287 231 250 205 261 188 191 10 92 91 282 30 87 158 257 30 265 160 234 243 285 21 167 96 144 47 240 107 274 17 130 211 301 55 259 73 286 207 298 42 123 12 127 92 153 78 193 126 140 58 307 70 299 68 130 18 202 34 310 172 177 98 190 21 151 91 149 102 159 100 162 22 69 42 135 17 196 68 310 101 298 83 236 81 310 53 154 170 175 152 232 219 294 57 163 15 253 93 182 60 311 81 25…
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: 1605 1062 477 1496 29 1368 164 1551 310 532 715 1030 1214 1517 974 1308 1250 1267 41 104 855 1225 234 616 325 661 59 324 69 1545 131 618 643 1067 69 986 200 289 1134 1327 237 1594 258 1022 461 591 979 1587 1147 1537 773 1553 265 1105 450 795 211 276 526 543 1081 1214 13 1604 586 711 57 402 1415 1499 332 1347 355 1311 53 923 167 348 89 1510 918 1240 236 1545 235 776 1233 1246 1446 1599 350 377 1306 1340 671 701 170 621 18 740 602 1246 572 1553 747 1103 885 1436 83 1166 35 1020 448 1477 1398 1596 1066 1068 1160 1517 545 884 1332 1551 326 480 1383 1602 645 1462 951 1114 1250 1508 180 1150 566 1057 1113 1570 679 916 1007 1320 135 934 263 1449 1400 1457 504 739 883 1067 500 864 1345 1455 333 432 677 880 434 904 262 1210 1248 1587 305 893 796 1215 358 987 200 1145 966 1103 811 1465 427 862 292 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: 711 1163 146 429 242 387 542 603 118 382 166 542 38 204 6 23 416 605 130 236 89 282 216 305 519 552 209 683 50 686 195 616 378 582 29 452 363 517 297 584 370 417 167 454 88 456 289 535 147 578 529 658 548 642 36 632 76 171 305 321 130 403 381 505 147 561 113 140 487 527 231 452 101 481 150 507 64 443 357 398 194 552 430 684 208 320 73 523 280 324 56 328 492 506 459 467 76 191 358 697 105 496 214 610 352 586 124 528 256 695 663 694 323 346 188 220 63 284 614 647 36 494 479 562 94 104 111 164 92 375 352 670 29 601 401 435 322 444 176 683 335 410 143 276 240 667 24 215 623 670 145 179 170 705 120 275 351 668 129 466 482 489 224 531 19 314 111 314 378 653 11 61 200 666 247 501 557 671 374 376 22 299 552 563 159 628 222 288 318 320 516 540 232 599 101 661 330 709 39 692 218 637 491 511 41 110 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 …

Constraints:

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

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