CT51713

Vera's Fewest Hops Ledger

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Vera found an old ledger of tunnels in the aviary attic at the tulip beds of Bloomhaven. 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 <= 2644; 0 <= m <= 5288.

Example 1:

Input: 1938 4821 1 1938 1135 1287 412 1338 104 1740 1578 1620 1104 1722 234 451 656 1669 316 879 749 1791 50 1932 427 1627 107 1891 285 1118 164 854 82 1274 137 221 641 991 897 1173 783 1369 350 1344 708 1777 1335 1850 31 310 704 1767 1495 1699 111 382 607 1417 595 1073 211 266 991 1393 213 545 397 1857 510 560 989 1917 1028 1615 611 693 278 909 892 1491 70 923 82 1881 1202 1523 1282 1708 1068 1368 692 769 992 1889 1555 1697 1118 1813 164 1613 944 1302 1127 1132 305 1113 813 1415 150 218 732 1744 904 1327 296 611 1099 1176 1090 1797 604 1091 328 1440 80 1419 879 1424 380 1649 279 1703 16 731 221 1283 542 1339 414 1462 663 1331 847 1315 44 128 1043 1213 1146 1540 1478 1762 607 855 177 1371 1558 1710 655 1193 12 1725 155 1825 210 791 680 1065 455 1793 362 1715 362 1337 1729 1803 832 1817 206 1870 2…
Output: 3

Example 2:

Input: 27 351 1 27 3 13 5 7 25 27 7 17 20 22 7 8 5 8 3 20 2 9 5 17 8 18 9 12 11 18 11 15 13 16 2 3 6 23 8 13 23 27 1 12 18 23 2 6 6 14 16 18 7 10 15 22 1 22 3 8 14 16 10 21 8 17 12 27 9 17 8 22 3 10 1 5 19 27 4 26 17 18 3 12 1 16 13 21 8 11 16 17 22 23 7 13 18 26 5 22 9 20 22 27 14 18 8 23 12 26 2 20 8 27 22 25 21 24 11 27 6 15 1 14 2 19 8 9 12 19 5 10 17 22 1 2 4 21 1 4 10 13 1 11 16 22 6 24 6 19 9 15 15 21 15 27 6 13 8 21 12 23 18 24 23 24 10 24 2 18 10 12 11 13 11 23 11 21 6 10 4 18 6 17 2 10 3 22 1 15 6 12 16 24 13 24 4 9 15 17 10 26 19 25 3 23 16 20 11 14 1 26 3 24 19 21 3 18 4 19 3 19 4 15 3 27 4 11 10 27 2 13 2 27 20 27 1 18 8 10 6 26 12 14 20 21 6 11 16 27 9 14 14 19 14 20 13 15 1 17 23 26 12 18 9 11 7 24 6 9 12 15 19 26 24 25 2 14 6 21 5 18 4 25 9 24 5 25 3 15 13 18 5 15 8 26 1 23 4 10 1…
Output: 1

Example 3:

Input: 1942 1941 1 1942 1246 1529 1142 1205 1161 1243 1727 1756 908 1059 86 1124 310 1655 1517 1526 1427 1811 890 1904 677 1146 1078 1867 810 1469 586 741 485 1745 664 965 934 1539 1549 1675 1312 1941 779 1851 1224 1756 609 1342 145 1691 1801 1845 819 1082 279 844 93 339 862 1598 1397 1766 510 1742 751 1098 1250 1600 1065 1850 580 1343 158 1315 1256 1666 784 1677 513 706 179 283 627 1293 564 1340 921 1919 197 1340 1123 1203 664 1820 739 1640 655 774 738 1868 121 974 498 822 106 1359 659 1858 596 947 305 660 841 1356 918 1106 1012 1844 375 1160 332 1704 1847 1929 203 496 954 1697 1342 1866 991 1451 71 663 382 1072 577 1875 69 1437 1493 1627 651 1462 329 1391 196 886 153 533 74 1091 1767 1910 863 1787 515 1032 1541 1879 523 1604 1196 1262 648 1436 1004 1333 608 1170 703 1927 1462 1661 132 255 541 1…
Output: 13

Constraints:

1 <= n <= 2644; 0 <= m <= 5288.

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