CT46649

The Build Order Beneath Barkhaven

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Legend says the vault under the cork grove of Barkhaven opens only for a perfect tally of routes. Shepherd means to find out. 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 <= 2922; 0 <= m <= 2922.

Example 1:

Input: 1257 2167 387 481 16 777 974 1160 22 198 433 735 543 897 11 519 700 825 114 655 111 753 77 297 884 1186 589 774 53 871 144 373 963 972 891 956 1106 1111 203 208 797 1256 551 907 239 1024 869 990 297 972 869 1028 111 265 182 1138 847 1022 272 1198 445 772 33 181 146 529 624 686 653 1135 294 362 639 1160 428 1208 29 1135 770 804 727 866 652 1153 565 1117 412 1003 735 975 455 621 682 993 218 524 190 1176 57 902 495 1158 172 847 782 1066 983 1251 980 995 275 1045 461 1125 337 1123 525 826 88 1137 400 682 217 1075 372 1001 296 693 269 521 611 864 109 1051 579 592 705 1168 640 1118 685 1156 295 672 72 932 314 393 84 1035 454 776 681 895 294 580 148 415 346 778 1037 1045 608 614 593 624 234 980 1004 1217 641 845 264 1019 1075 1194 1162 1191 309 348 683 788 288 317 601 1154 299 910 316 694 92 675 …
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: 815 741 105 559 396 541 402 437 83 183 396 519 266 485 710 800 190 256 137 698 193 425 19 538 448 656 392 657 228 551 143 249 425 564 71 427 95 792 120 239 580 717 180 748 257 265 119 499 461 772 236 542 548 688 613 723 89 380 554 737 73 567 20 604 276 444 410 798 56 681 321 755 384 508 530 680 119 561 43 101 265 639 195 304 252 628 160 618 87 204 272 769 64 161 18 135 84 114 445 658 500 762 433 629 234 506 402 789 59 344 383 730 47 80 220 586 194 399 363 430 336 415 272 330 143 767 87 571 147 394 61 175 289 749 123 251 468 573 714 807 14 528 376 726 264 733 328 429 438 742 18 151 358 793 225 471 578 650 112 243 24 48 330 741 142 226 68 773 274 566 179 804 220 233 404 511 40 474 71 703 783 796 377 511 153 442 410 783 185 506 167 761 498 750 257 391 395 416 85 207 2 216 327 484 87 106 16 69…
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: 350 2164 37 348 146 216 24 224 13 243 74 144 91 180 165 319 13 114 42 90 111 340 30 66 84 319 10 244 174 221 24 290 64 303 6 15 38 246 1 120 68 161 7 300 57 297 16 27 25 320 333 350 77 284 99 273 68 171 16 173 295 344 303 335 226 329 212 266 166 211 278 289 280 332 276 284 108 220 134 283 174 284 207 255 119 196 112 201 90 301 11 226 243 341 88 101 91 130 32 280 12 191 206 313 152 183 126 324 36 275 21 332 28 239 30 298 176 190 44 64 35 51 279 318 206 348 82 130 236 340 265 339 207 273 12 62 7 307 63 159 181 249 39 118 26 65 306 323 28 285 58 246 23 321 212 277 226 230 37 263 119 260 134 182 38 125 245 246 43 347 27 317 138 288 183 349 79 166 183 212 182 233 47 154 203 294 334 341 60 105 303 311 20 308 137 163 99 343 132 254 214 253 71 110 331 334 4 257 81 273 15 183 33 195 318 332 25 222 …
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 <= 2922; 0 <= m <= 2922.

Loading...
Test Cases:No test cases
No test cases available.
The Build Order Beneath Barkhaven - MEDIUM Coding Problem | CodeTikki