CT35687

The Chessfield Fewest Hops

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Morning light hits the rook towers of Chessfield as Yami unrolls the day's manifest of tunnels. The tally will decide the next shipment. 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 <= 2663; 0 <= m <= 5326.

Example 1:

Input: 2166 2165 1 2166 773 950 941 1778 787 868 24 2023 81 851 347 1439 636 1103 238 707 216 479 139 1207 743 1117 786 1056 62 1956 287 2062 909 1263 146 2072 185 2154 1836 1891 436 1208 902 1832 231 1887 634 1664 142 507 410 1015 682 2110 945 1068 616 1578 358 767 1405 1886 988 2063 170 1449 779 1905 776 798 941 1149 198 854 346 650 1174 2020 590 701 241 409 1101 2137 1296 2152 1902 2002 608 1908 1051 1654 1922 1925 455 1566 583 1335 789 960 195 297 305 799 1567 1845 916 1780 1120 1899 557 1351 50 716 966 2116 1417 1738 1002 1921 771 1548 249 1949 785 1194 1470 1831 982 1105 649 1201 747 1464 1019 2018 1119 1965 851 1646 726 1088 607 2113 1608 2088 630 1932 207 1740 384 1239 690 1166 4 932 1051 2152 108 663 745 869 910 1774 390 1020 1642 1741 1417 1712 54 1017 1047 1412 245 2137 1478 1929 520 1…
Output: 8

Example 2:

Input: 1363 2914 1 1363 1293 1313 106 1242 5 186 762 1312 679 696 622 1300 187 997 62 145 127 1296 147 693 52 744 845 852 113 661 181 510 1192 1264 138 281 682 756 738 1184 166 212 166 1159 258 1338 46 272 207 863 339 343 253 1226 56 102 418 922 181 546 1255 1330 448 991 348 779 121 1336 498 1079 1067 1282 149 707 459 767 460 1212 284 1130 840 877 271 452 395 594 1193 1202 300 1131 276 930 344 805 28 1332 1331 1347 131 1000 871 914 407 1328 473 749 14 509 198 774 979 1345 564 793 144 1210 259 716 38 325 604 938 556 1150 311 693 173 576 465 1220 332 997 1094 1241 33 231 249 256 643 810 309 1191 712 852 227 351 347 1226 1135 1144 374 792 463 915 130 422 677 1041 273 913 219 1002 845 918 956 1105 657 1300 830 1187 133 1102 366 1281 1070 1307 21 992 455 1360 347 793 338 1256 342 454 526 1107 825 1075…
Output: 4

Example 3:

Input: 2268 2267 1 2268 1017 2116 761 1774 1583 1651 635 993 106 1405 798 947 143 747 46 1560 809 1820 1068 1322 815 2209 314 842 87 1248 573 1925 518 1410 973 2141 2036 2237 819 1257 1700 2139 1287 2008 9 151 1063 1208 766 1732 37 1021 55 689 558 2069 612 1331 39 738 1161 1771 1365 2194 1739 1836 138 928 132 1614 1108 1281 912 1402 934 1409 321 2003 66 1128 390 1601 15 835 817 1950 1134 1974 1733 1819 149 1867 1331 2074 245 1740 698 973 951 2011 283 846 403 2089 1216 1568 1247 1391 715 809 1104 1762 181 1060 337 499 1475 1631 126 190 2038 2102 436 1314 272 524 241 1061 1090 1185 1696 2114 242 1169 165 1646 1156 1492 144 329 1351 2091 20 2156 815 1260 449 994 75 130 364 387 669 1293 1261 1505 786 948 50 608 2025 2169 634 1434 1067 1499 1846 1903 824 1904 350 1674 1051 1421 338 1783 1404 1866 425 …
Output: 7

Constraints:

1 <= n <= 2663; 0 <= m <= 5326.

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