CT55932

The Caramel Build Order

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Every season at the peat bogs of Mossgrieve, someone must balance the workshop's books. This year the task falls to Yusuf, armed only with the tunnels register. 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 <= 2077; 0 <= m <= 2077.

Example 1:

Input: 1374 542 533 874 300 646 107 1053 395 1176 46 768 421 574 794 991 334 1171 220 1332 871 1236 842 1239 1198 1371 436 973 101 935 658 1197 607 701 1251 1269 1196 1275 467 784 298 635 274 951 127 726 322 947 450 1132 1057 1305 684 1210 604 680 584 1267 512 1009 5 1347 729 1037 522 1198 989 1070 388 815 59 511 789 1097 382 569 898 1168 209 554 1200 1357 226 841 124 143 1096 1243 145 785 569 832 930 1216 435 647 672 1054 836 958 763 1325 434 1009 266 1127 742 779 535 1038 554 866 667 1124 334 540 572 1186 168 667 672 978 83 1059 332 866 930 1029 782 1168 681 1316 982 1036 531 836 6 373 221 436 452 817 330 1243 821 929 62 294 475 815 309 851 930 1366 261 431 1212 1217 1235 1363 238 1070 203 1258 373 901 644 1036 662 956 220 470 402 475 48 339 607 858 259 1024 9 622 92 319 599 746 1067 1267 992 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 2:

Input: 1037 399 144 595 107 838 503 750 730 988 4 619 364 726 231 911 374 440 382 892 513 758 409 962 339 371 542 775 288 890 138 878 533 842 323 490 17 143 559 967 586 782 214 477 245 875 53 473 645 792 188 969 41 103 551 591 103 271 132 448 281 574 182 1011 98 280 169 410 69 380 379 794 80 120 748 987 88 213 347 872 48 807 663 999 335 980 30 388 441 850 441 662 572 989 67 144 531 920 493 693 45 582 404 827 383 929 627 961 52 406 191 238 525 877 636 821 289 1032 529 625 864 899 79 171 497 586 91 264 462 904 241 582 11 575 836 911 204 610 151 954 268 395 399 950 594 712 287 364 159 365 283 1020 161 818 129 273 403 556 234 793 277 766 563 891 374 969 411 445 360 660 179 719 586 896 78 130 106 172 448 1007 286 567 471 556 48 627 99 863 676 857 38 729 296 368 213 1003 428 632 380 629 332 813 131 102…
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: 636 830 195 265 8 185 117 426 368 371 104 369 83 239 141 167 376 526 383 616 142 474 89 626 541 584 247 333 499 613 292 613 327 545 207 421 332 605 343 496 24 295 194 562 105 215 448 455 10 19 227 606 105 359 520 526 234 468 555 609 129 510 363 553 313 633 48 401 204 562 290 467 82 116 342 498 171 315 128 164 28 591 208 297 111 369 324 381 249 328 311 424 54 71 107 628 222 529 192 506 217 494 158 313 36 490 344 623 52 295 59 475 97 193 22 307 56 201 329 562 448 551 314 463 291 454 314 320 325 571 455 479 148 169 85 218 287 484 447 599 171 505 353 432 295 298 251 636 190 206 300 377 13 569 382 518 61 73 329 591 118 515 469 560 26 472 409 436 297 359 82 368 67 148 259 503 3 163 626 636 93 147 32 240 342 439 383 426 177 205 43 469 184 188 137 542 29 110 129 216 160 435 545 574 188 459 38 268 …
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 <= 2077; 0 <= m <= 2077.

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