CT64343

The canals at Briarthorn

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Vani found an old ledger of canals in the brewery attic at the forest village of Briarthorn. The margin notes pose a precise question. 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 <= 1147; 0 <= m <= 1147.

Example 1:

Input: 653 489 128 436 308 555 116 262 228 519 292 559 133 244 401 646 115 143 40 275 69 244 566 610 211 513 90 252 493 589 435 445 188 470 5 125 301 399 173 492 75 264 97 442 58 105 167 452 87 531 50 51 172 509 241 264 84 313 190 462 172 278 55 520 164 608 84 286 84 496 144 574 42 244 33 562 130 418 310 652 295 653 465 604 20 418 52 584 96 609 341 473 153 314 30 296 207 653 104 302 93 248 320 554 15 18 535 609 210 264 49 628 449 513 305 614 346 610 273 554 324 543 371 651 45 570 108 542 133 379 312 382 252 440 201 346 19 444 229 293 250 484 178 412 377 589 361 477 85 450 42 134 454 511 294 483 328 554 125 338 306 490 13 230 404 602 184 307 217 411 238 465 74 634 104 325 50 608 75 266 26 101 112 457 275 413 212 340 158 319 135 186 301 462 211 598 219 310 416 469 34 131 292 416 95 297 235 638 137 …
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: 649 70 109 516 113 340 66 396 136 469 25 527 264 539 349 402 78 486 53 456 169 295 38 221 13 607 179 356 563 607 277 587 237 351 228 449 165 426 307 321 22 603 128 534 379 530 448 539 359 397 165 448 255 459 18 192 91 530 121 216 207 581 363 449 337 634 202 293 82 339 55 636 104 436 466 598 220 539 578 628 208 263 407 616 202 542 114 593 513 600 276 380 426 590 82 439 80 273 207 625 521 619 630 638 173 230 48 170 374 417 5 457 350 544 257 476 577 604 6 325 48 355 53 258 307 614 47 396 453 542 50 541 10 260 214 322 325 648 107 469 360 639
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: 934 283 341 589 49 499 347 441 832 929 226 449 202 571 714 817 334 684 613 921 71 508 1 899 60 414 279 354 144 301 594 758 287 376 474 664 315 868 115 478 31 865 610 718 517 690 442 509 282 568 332 738 206 377 580 759 108 549 48 609 318 620 56 481 103 313 271 818 529 867 199 654 20 493 459 502 302 788 259 785 88 744 50 408 183 815 101 625 61 359 111 166 311 673 198 654 155 630 729 767 2 440 263 737 626 691 123 174 177 340 345 823 291 832 388 606 237 868 382 744 667 922 327 908 199 210 200 309 301 787 93 615 101 681 246 397 704 738 307 827 190 491 188 624 569 735 81 493 361 528 245 784 268 605 431 870 124 182 676 819 374 476 97 556 38 346 328 817 555 634 185 622 458 537 173 896 131 727 135 681 163 458 559 922 556 845 449 724 226 643 3 553 401 833 78 690 26 541 609 829 131 324 217 524 12 119…
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 <= 1147; 0 <= m <= 1147.

Loading...
Test Cases:No test cases
No test cases available.
The canals at Briarthorn - MEDIUM Coding Problem | CodeTikki