CT35652

Draper's Ledger of canals

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

The assayer Draper has been asked to rank apprentices for the new term. On the desk lies a long table of canals readings. 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 <= 2903; 0 <= m <= 5806.

Example 1:

Input: 2299 4098 1 2299 290 1005 110 617 1433 2194 953 2248 1057 1740 179 1228 1632 1800 1468 2089 1916 2081 1356 1912 1078 1203 723 1423 1271 1493 82 2134 1065 1905 782 1554 1456 2277 594 751 1035 1070 1549 1753 1892 1934 513 2284 312 1464 104 2240 1530 1840 359 1640 1088 2100 251 1429 777 1592 1026 1569 639 1497 1246 1510 1424 2211 1242 2082 389 1235 252 970 66 605 20 1684 249 2130 1745 2292 769 1015 569 2237 490 1245 645 2157 1546 2207 410 1710 653 774 897 1963 203 445 1438 1706 73 1636 1547 2265 55 1823 294 1792 988 1350 116 1822 224 1526 1646 2264 249 1883 823 1487 438 1446 750 2069 984 1580 1779 2190 923 1567 326 1084 911 1254 1519 1608 374 1600 1673 1808 1816 2069 1787 1945 1605 1616 1152 1990 1298 2147 891 1078 429 2166 1858 2075 1588 1923 1459 2081 104 1418 702 1378 1232 1770 184 764 477…
Output: 6

Example 2:

Input: 2068 2067 1 2068 1171 1568 59 553 1471 1564 220 601 26 1145 187 1833 70 541 1601 1804 594 1888 1032 1422 1068 1265 36 1828 1204 1510 200 319 1279 1430 1226 1669 132 1235 720 1674 592 1285 1701 1963 510 1522 667 1736 1600 1749 410 1094 1282 1737 750 1754 177 828 142 948 758 1848 329 1029 596 1604 127 1248 757 1983 646 2066 1420 1480 303 1805 487 1833 225 1463 385 555 153 1691 105 2020 662 1374 334 689 650 1600 244 536 486 1305 613 1239 254 1434 470 708 269 845 312 543 605 1328 238 760 123 310 882 1690 164 1717 631 959 57 1464 1362 2019 842 1053 1639 1866 443 1743 932 1422 1257 1293 79 835 446 867 751 829 1407 1995 1088 2008 345 828 1268 1657 1432 1594 1470 2020 1373 2041 1567 1810 1583 1597 1413 1578 162 1002 183 814 97 158 1927 1996 435 1312 102 653 836 1317 329 1096 241 437 476 1210 63 15…
Output: 12

Example 3:

Input: 1400 4681 1 1400 544 1386 511 1389 782 1309 377 509 54 1292 875 1017 483 1222 419 1343 861 1154 101 647 139 1389 459 1399 195 1298 852 1143 250 769 1008 1218 143 1209 632 696 1012 1251 949 1343 401 878 373 1365 1215 1314 342 1259 65 841 526 690 282 1158 159 292 1206 1209 777 848 416 550 357 1085 400 630 629 1103 602 1325 725 1035 238 780 165 481 188 356 300 1136 467 483 172 240 861 1161 266 871 209 1063 207 418 90 1156 386 1006 525 1218 254 823 230 861 108 1313 511 677 36 845 289 787 1337 1398 5 394 1122 1212 730 959 705 1174 309 1397 303 713 806 1134 49 1258 467 1210 775 788 8 389 384 858 712 963 552 1335 188 757 130 737 638 1090 307 1060 153 522 429 951 99 244 13 841 209 1152 929 1124 1035 1209 113 121 132 285 362 871 57 1208 398 758 363 450 268 402 262 360 218 221 29 1069 798 1172 221 6…
Output: 4

Constraints:

1 <= n <= 2903; 0 <= m <= 5806.

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