CT32344

Esha's Fewest Hops Ledger

MediumL4 · Loop LordAcceptance: 0.0%XP: 35

Legend says the vault under the savanna camp of Amberplain opens only for a perfect tally of corridors. Esha 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 <= 1239; 0 <= m <= 2478.

Example 1:

Input: 1065 1123 1 1065 4 469 788 1002 404 991 104 390 112 738 515 1035 501 944 97 195 788 845 374 481 211 345 225 685 505 803 597 828 534 992 124 142 396 733 297 708 435 468 531 866 429 747 549 927 106 339 188 987 163 753 475 984 456 495 82 935 411 590 96 498 272 587 472 748 768 847 823 932 188 970 515 719 959 1002 131 747 99 210 302 744 747 859 579 901 19 676 472 1061 11 608 173 448 13 871 571 714 206 387 470 707 585 889 207 628 220 593 854 896 33 663 10 817 316 876 348 930 344 873 666 1022 181 197 968 1045 82 296 247 733 147 382 837 1012 149 867 412 958 351 865 290 552 747 1050 68 155 467 739 37 403 56 321 47 963 104 660 579 788 140 712 351 978 53 54 460 582 171 704 591 752 673 974 460 491 256 1023 85 942 108 994 148 1047 334 650 44 233 159 234 50 95 152 902 517 717 292 314 449 1005 712 964 90…
Output: 8

Example 2:

Input: 809 2240 1 809 23 527 327 550 154 593 422 710 5 679 339 594 60 550 187 614 489 579 198 216 86 410 320 348 77 787 14 698 57 354 150 730 93 231 296 648 461 554 602 807 438 500 102 203 44 371 90 325 29 628 136 228 287 507 3 289 135 615 224 407 313 329 713 788 479 621 187 706 194 683 71 246 48 567 681 683 8 531 231 249 10 604 280 300 54 244 568 577 55 444 609 679 570 630 279 740 53 74 93 722 440 502 371 448 348 649 24 603 101 297 52 129 1 608 305 733 398 607 436 488 268 313 250 425 468 572 615 674 424 595 16 427 184 362 165 497 201 292 369 484 209 268 258 709 188 585 182 620 185 367 63 258 111 386 677 754 22 525 125 254 450 756 164 728 470 558 170 345 209 556 185 370 19 402 422 571 33 489 175 659 537 709 565 785 70 227 358 650 543 647 529 639 359 521 109 339 327 483 442 741 528 611 477 556 13 …
Output: 5

Example 3:

Input: 1183 1684 1 1183 274 605 370 1164 172 366 392 1079 914 941 510 1054 294 494 223 608 421 1128 469 810 342 586 662 698 237 309 707 748 200 1009 157 1058 530 791 94 636 230 424 260 626 98 1035 147 1095 756 1060 1 851 11 219 311 526 130 712 404 610 928 1113 658 1024 590 927 60 98 613 892 298 355 94 1088 770 1049 964 1102 111 391 433 1118 28 547 877 1009 49 835 354 884 588 656 399 1143 135 185 663 683 7 814 846 1153 672 694 776 1047 77 145 270 415 797 1080 15 147 644 777 174 742 242 700 209 748 389 873 144 1147 825 1157 895 901 732 770 305 676 18 1055 540 761 100 554 167 1057 801 877 127 516 369 697 170 1131 662 860 581 963 134 313 973 1078 356 401 806 982 647 730 374 898 115 202 340 910 323 407 395 588 71 911 547 629 1068 1139 691 863 1078 1144 30 889 149 190 150 943 518 1062 367 882 525 1027 …
Output: 2

Constraints:

1 <= n <= 1239; 0 <= m <= 2478.

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