CT31263

Bishop and the Fewest Hops

MediumL4 · Loop LordAcceptance: 0.0%XP: 35

Bishop found an old ledger of routes in the salt store attic at the archive halls of Scrollkeep. The margin notes pose a precise question. 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 <= 1086; 0 <= m <= 2172.

Example 1:

Input: 36 630 1 36 4 26 23 32 5 28 15 36 4 15 5 32 16 24 10 36 21 24 4 34 9 17 35 36 3 30 16 28 17 20 18 30 11 13 22 35 15 22 6 22 21 26 4 6 15 16 14 28 26 27 20 23 21 25 12 34 5 21 8 30 25 27 25 36 12 22 2 12 3 17 4 22 15 18 9 15 1 24 10 17 25 31 2 25 23 33 14 34 2 29 13 36 2 35 27 30 16 23 26 30 34 36 25 33 4 5 3 11 19 34 14 19 9 35 4 29 11 29 7 36 17 23 5 36 15 27 1 11 11 26 19 21 1 22 9 36 2 9 31 35 12 13 20 32 15 25 17 30 10 13 5 8 2 19 24 34 21 34 2 10 3 28 14 24 6 12 7 21 12 17 9 32 14 23 15 33 1 12 6 23 30 36 3 35 5 34 18 32 5 19 10 35 5 29 8 31 1 30 3 14 14 29 7 23 10 12 9 29 7 27 25 35 8 35 27 29 20 27 19 24 9 13 6 36 4 25 2 13 14 18 4 18 27 33 23 34 3 19 19 25 22 29 5 22 10 15 28 32 13 21 18 33 2 30 18 34 4 17 6 17 24 30 34 35 7 15 3 36 16 35 12 33 23 35 20 26 3 15 6 27 7 11 11 12 17 2…
Output: 1

Example 2:

Input: 712 711 1 712 307 401 73 443 566 574 393 656 337 451 537 675 209 581 47 295 580 688 185 691 187 391 298 320 557 641 60 578 581 702 162 242 13 595 383 399 145 586 426 502 507 609 106 111 182 704 19 215 266 328 398 424 102 363 423 622 561 587 351 677 42 604 517 687 121 571 14 536 240 503 330 704 27 75 247 712 221 444 506 624 516 526 99 283 568 705 188 239 137 653 231 578 333 454 231 453 103 494 137 247 71 598 328 571 279 507 69 611 647 678 341 386 252 564 171 387 132 301 581 678 240 392 139 569 618 670 1 137 20 451 287 371 556 565 34 358 51 598 30 672 198 414 270 348 160 307 247 600 417 657 159 417 4 151 128 396 514 606 563 700 514 624 136 316 7 383 121 235 245 272 83 654 231 234 52 550 48 486 511 551 166 464 226 700 334 559 69 173 192 614 492 534 169 188 56 569 334 497 364 610 435 438 559 6…
Output: 3

Example 3:

Input: 905 1348 1 905 493 882 658 729 71 622 743 812 228 385 96 180 28 262 322 725 302 632 74 87 572 592 456 633 526 635 143 672 208 832 14 547 189 827 6 677 303 833 398 549 492 530 107 319 217 403 761 895 308 413 697 889 581 732 178 904 257 776 670 795 69 798 82 670 29 675 472 688 107 478 236 341 141 205 92 388 562 698 183 883 565 687 376 734 569 763 261 262 87 309 229 272 250 869 440 527 52 120 133 559 35 636 369 766 316 695 450 895 359 861 496 647 397 814 38 466 92 464 848 870 177 410 11 377 744 824 374 866 272 592 570 865 364 726 310 619 407 528 572 714 408 575 312 503 611 673 163 547 118 377 55 245 225 505 852 898 165 356 103 162 380 511 110 500 523 878 482 823 610 818 45 596 279 874 557 859 255 520 103 665 72 242 591 688 84 88 153 189 594 796 94 200 643 831 374 879 433 702 412 688 825 852 1…
Output: 6

Constraints:

1 <= n <= 1086; 0 <= m <= 2172.

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