CT57034

Dino's Twilight bridges

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Legend says the vault under the tulip beds of Bloomhaven opens only for a perfect tally of bridges. Dino means to find out. Task: Print the minimum number of edges on a path from s to t, or -1. Input format: First line: n m s t. Next m lines: u v. Output format: Print the BFS distance or -1. Constraints: 1 <= n <= 1198; 0 <= m <= 2396.

Example 1:

Input: 853 1975 1 853 361 381 12 196 338 702 150 806 490 672 502 771 301 429 167 443 376 758 156 409 257 567 140 151 440 803 357 442 635 646 102 576 337 847 173 798 121 348 105 112 14 579 723 739 6 650 466 665 194 299 116 781 83 310 145 401 20 507 405 499 334 543 546 653 75 812 12 85 167 598 20 776 399 469 54 634 770 811 189 438 521 820 493 673 102 538 472 604 202 289 34 545 359 726 661 760 180 489 15 597 557 710 529 722 288 419 246 493 109 148 360 741 55 600 294 734 439 626 29 160 9 573 117 123 625 726 124 391 5 81 328 731 417 664 417 606 697 821 204 214 84 243 251 669 471 648 569 669 182 424 355 364 14 746 453 791 624 792 41 140 139 815 16 500 631 804 439 495 16 655 646 789 148 793 34 413 219 341 9 810 487 846 71 578 82 483 13 364 608 852 353 829 89 113 642 757 65 540 225 578 64 93 513 545 769 …
Output: 5

Example 2:

Input: 69 156 1 69 9 38 13 41 4 25 32 45 2 19 30 67 19 21 51 55 31 33 52 54 4 37 10 46 6 21 4 28 62 66 47 64 26 57 35 47 2 15 22 40 10 18 43 62 32 64 10 51 7 11 33 50 16 17 50 53 25 28 27 64 2 32 23 37 16 54 15 44 10 62 42 57 35 48 35 60 51 61 4 14 15 22 12 33 5 22 6 11 18 46 7 36 21 53 19 45 7 65 18 25 1 20 18 61 24 57 45 68 58 66 9 32 52 64 9 46 40 68 10 52 32 59 57 60 49 68 34 67 21 35 31 57 20 28 3 61 43 54 6 59 24 66 25 54 33 42 13 68 15 35 29 45 2 12 12 52 4 53 33 38 8 61 15 27 1 17 28 48 10 55 11 31 51 57 9 52 12 55 10 64 13 15 1 52 61 69 12 16 2 23 17 37 33 62 23 33 35 66 27 33 35 39 4 47 46 56 24 34 24 37 44 52 20 42 13 50 28 44 1 39 29 67 25 56 6 17 45 46 1 22 27 65 21 31 36 66 8 48 12 14 23 26 23 58 13 53 32 63 4 41 26 67 31 37 4 38 22 44 26 38 7 50 22 55 22 60 49 58 9 64 48 53 11 65 1…
Output: 5

Example 3:

Input: 815 839 1 815 310 792 344 750 218 419 30 402 351 423 16 562 431 540 108 231 448 482 247 259 7 256 46 372 155 550 651 682 175 619 290 753 85 559 29 600 12 175 195 712 129 470 14 507 433 652 587 665 593 782 104 269 12 723 115 659 319 661 486 621 355 742 491 583 282 702 243 414 126 796 176 441 7 28 13 631 504 762 48 342 14 437 177 409 354 383 228 541 271 302 198 562 1 178 91 213 239 505 608 614 296 603 15 101 128 722 521 636 343 643 135 415 582 756 495 703 272 537 749 773 297 670 444 758 523 587 23 780 413 623 398 503 629 657 78 696 574 694 155 165 14 585 302 779 381 652 121 565 175 746 406 684 36 162 218 528 280 714 153 477 103 551 278 748 399 627 149 363 255 624 283 642 374 490 44 633 189 586 51 648 146 216 2 98 189 812 148 734 257 590 89 683 336 800 267 556 294 423 176 199 82 109 71 617 46…
Output: 10

Constraints:

1 <= n <= 1198; 0 <= m <= 2396.

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