CT47609

The Rootwater Fewest Hops

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Every season at the mangrove channels of Rootwater, someone must certify the cargo before shipping. This year the task falls to Baker, armed only with the routes register. 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 <= 3342; 0 <= m <= 6684.

Example 1:

Input: 747 6421 1 747 325 580 380 506 641 648 35 356 154 301 690 700 426 720 374 495 173 258 22 392 209 330 284 386 155 644 290 567 186 615 273 431 9 346 112 159 25 453 289 298 410 731 623 658 586 686 12 93 154 702 156 629 20 547 149 493 128 331 231 267 268 430 18 481 249 671 198 483 538 625 29 172 229 251 165 584 392 394 109 181 308 405 487 494 427 457 8 375 24 86 19 732 573 724 635 642 102 571 616 704 64 718 302 509 612 713 705 730 276 737 463 663 227 608 18 255 121 480 179 625 439 461 393 680 139 739 197 739 64 641 397 502 262 649 215 330 256 636 42 666 266 446 186 561 164 611 393 666 497 523 428 745 352 380 107 341 74 142 436 689 59 580 249 385 90 433 200 477 211 287 488 554 149 461 26 630 32 489 229 581 52 154 560 570 123 685 110 287 198 681 595 667 2 268 242 539 77 613 525 643 83 399 247 46…
Output: 3

Example 2:

Input: 2818 2817 1 2818 287 2427 1361 2056 317 1881 1349 1776 88 895 49 1009 1007 2548 1490 2313 266 1638 387 798 137 1813 1234 1482 659 1771 1687 1780 1664 2212 670 965 435 1512 1662 2202 861 879 546 1487 487 2684 687 959 1504 1517 1553 2108 804 1458 149 2082 1146 2598 172 314 322 2041 1916 2076 1931 2452 2250 2753 1337 1530 2405 2440 530 2604 548 2723 484 2477 824 1252 1670 1973 1368 1820 130 176 2577 2711 1400 2740 587 935 690 1920 217 1987 2049 2586 2155 2535 373 1417 56 588 658 1303 563 2076 1178 2201 2049 2222 550 993 64 1866 111 2369 1109 1159 863 2539 774 1458 1094 1790 1134 1707 671 2075 693 2605 1754 1940 312 1226 448 599 1158 2251 280 1053 1150 2812 484 596 688 956 189 886 1518 2705 1615 1869 605 2777 1516 1629 433 2404 11 1840 1962 2473 812 1481 569 1836 1015 1396 1810 2214 416 2191 2…
Output: 11

Example 3:

Input: 2506 4915 1 2506 73 781 1046 1303 579 1037 1751 1937 276 1939 165 1160 1633 2498 2171 2299 981 1718 279 1547 939 2323 2100 2219 272 1002 454 1606 192 1583 303 633 1530 1610 649 1100 99 1124 1321 1415 1765 2262 832 1932 546 1841 1804 1862 1977 2275 343 2174 1774 2097 1987 2470 179 1983 1422 1480 16 998 282 1578 2 1277 411 2032 1342 2258 1621 2453 851 1447 426 445 1646 2465 2121 2484 1617 1900 425 1668 414 1499 1302 1663 666 1734 1056 1238 216 244 1001 2106 1984 2424 637 949 607 1622 1034 1334 733 2275 974 1968 137 2418 71 1903 1275 1306 226 2018 49 154 2271 2477 365 833 658 2007 223 1108 648 1644 274 1928 324 1272 1262 1996 137 1410 688 827 774 2006 1696 2265 1699 2484 350 1129 1240 1430 1164 1251 398 968 761 1593 148 535 563 957 934 1204 1456 2458 502 1856 244 1555 815 1178 733 824 931 250…
Output: 6

Constraints:

1 <= n <= 3342; 0 <= m <= 6684.

Loading...
Test Cases:No test cases
No test cases available.
The Rootwater Fewest Hops - MEDIUM Coding Problem | CodeTikki