CT59061

The Build Order Beneath Marigold Row

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Caravans arrive at the saffron fields of Marigold Row with crates of canals, and Warden the auditor must account for every last one. 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 <= 2928; 0 <= m <= 2928.

Example 1:

Input: 601 243 86 160 258 359 379 554 266 559 13 353 457 537 189 395 376 397 405 551 111 559 506 583 297 498 204 534 201 233 289 454 221 288 304 434 469 485 414 487 28 190 11 424 96 239 45 112 151 305 104 263 154 512 10 312 91 133 319 474 310 536 365 533 284 393 174 185 193 425 135 357 36 350 319 558 508 564 3 64 110 244 61 68 246 373 23 24 381 388 463 481 94 221 144 376 532 591 51 296 216 413 171 518 165 352 189 231 263 453 236 490 72 373 139 229 247 434 148 497 553 572 51 238 379 541 244 433 412 492 246 485 9 278 224 580 286 398 60 505 83 247 127 514 303 475 392 585 50 327 232 325 101 340 98 211 399 424 286 383 342 354 109 347 404 415 219 435 192 471 286 436 2 298 413 591 137 466 409 498 237 598 173 269 107 487 154 446 381 486 72 137 59 192 255 336 408 422 47 494 380 457 140 158 374 444 29 155 …
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: 962 1121 765 773 622 766 611 692 425 508 730 819 171 288 737 811 330 594 264 443 208 433 250 749 211 436 2 431 82 566 735 944 418 622 25 372 95 303 147 608 99 369 685 722 513 664 507 517 276 452 385 872 640 945 47 273 127 177 602 603 348 768 461 824 668 696 700 840 48 770 97 672 79 92 500 730 135 528 186 794 372 406 159 721 167 495 753 849 423 868 369 504 255 816 334 944 405 816 282 526 544 767 309 827 133 851 497 777 357 468 466 680 536 925 112 431 442 741 451 909 141 406 201 680 647 859 463 511 277 819 371 559 385 908 160 595 326 823 366 556 76 108 346 956 670 958 354 370 298 459 101 805 124 915 758 811 861 953 204 271 105 808 465 748 126 161 166 953 51 695 789 867 359 837 485 653 744 960 12 780 498 868 36 539 203 373 160 672 260 414 716 768 93 397 829 899 341 951 130 189 434 436 612 911…
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: 1384 27 473 783 362 865 460 1018 112 1094 451 986 850 1248 298 387 55 743 1042 1238 347 1127 395 553 426 595 744 1273 623 1096 473 860 652 1373 385 507 308 377 79 1279 481 1272 422 1147 505 1384 356 907 17 1127 1161 1279 509 770 233 241
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 <= 2928; 0 <= m <= 2928.

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