CT50967

The Build Order of Goldmeadow

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Rhea inherited the kiln at the trading post of Goldmeadow along with its curious bookkeeping system for routes. Time to make sense of it. 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 <= 1326; 0 <= m <= 1326.

Example 1:

Input: 733 692 402 676 385 394 526 708 149 431 79 252 224 657 201 322 133 572 92 278 22 391 127 567 79 278 390 402 79 225 343 516 72 206 443 533 46 686 540 570 43 130 317 690 70 580 214 421 93 461 69 368 32 346 541 568 117 376 355 677 570 703 322 403 271 443 34 73 144 566 49 163 200 656 114 137 86 391 439 664 184 319 228 620 264 488 118 258 77 386 301 305 39 206 159 238 68 422 396 542 158 501 472 598 24 42 144 365 262 443 322 411 6 688 376 651 132 501 309 700 109 528 588 652 69 164 188 482 629 679 74 113 168 572 179 722 170 444 236 431 101 241 28 160 236 463 40 377 433 724 201 244 192 472 86 529 99 255 55 141 657 660 122 647 408 618 239 463 70 190 572 653 39 718 190 332 592 685 7 534 31 612 188 531 711 718 290 533 20 271 45 677 168 671 20 251 526 620 212 615 399 642 567 627 400 690 625 653 526 53…
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: 1159 1175 327 970 47 1000 281 765 213 365 237 945 403 1141 935 1093 190 1094 474 1086 74 372 629 1122 383 927 330 474 207 984 160 777 113 274 438 1000 234 403 923 972 573 851 443 809 137 1150 664 769 111 482 24 844 254 333 613 1011 218 1011 570 619 218 540 486 745 408 514 657 880 227 847 420 953 837 937 178 1083 683 1040 757 904 59 252 520 589 404 759 328 719 370 412 484 803 282 1016 237 362 227 591 136 1029 314 750 719 920 11 875 534 633 496 829 195 985 300 1004 735 831 304 414 184 304 764 1129 57 541 849 870 411 465 471 940 607 1132 388 680 287 637 321 704 16 751 286 755 939 1103 387 814 616 625 201 1064 107 215 530 1037 117 415 550 837 183 770 464 949 503 603 258 630 829 1003 172 902 325 704 992 1051 705 1052 363 1071 329 808 340 375 83 458 770 771 151 1041 239 1031 142 652 57 865 394 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: 650 208 185 373 21 537 78 562 45 108 427 537 93 166 131 421 284 463 222 265 254 561 194 344 51 111 147 391 12 151 344 550 306 313 93 373 214 259 200 576 51 68 433 607 348 557 219 630 2 141 44 87 81 428 137 252 18 330 551 615 115 147 110 566 119 372 440 593 226 544 225 468 309 483 483 559 270 303 99 454 7 581 247 534 246 386 248 369 47 493 151 253 241 320 112 497 300 468 390 421 399 430 481 508 586 614 252 622 155 176 356 565 46 461 260 523 299 348 491 590 27 564 390 507 201 370 459 532 141 204 185 449 273 312 374 382 66 286 152 201 233 641 334 564 9 537 520 627 156 548 191 497 251 445 352 620 99 529 44 54 325 474 314 366 112 278 406 462 38 444 111 397 222 460 158 262 275 306 16 22 131 312 104 610 278 310 397 615 126 181 255 476 415 468 76 270 179 582 480 614 237 341 47 550 386 605 253 641 …
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 <= 1326; 0 <= m <= 1326.

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