CT43522

The Fewest Hops at Glimmerfell

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

The reckoner Elsa has been asked to audit the season's records. On the desk lies a long table of bridges 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 <= 3885; 0 <= m <= 7770.

Example 1:

Input: 934 1222 1 934 121 899 260 458 185 392 418 845 42 316 170 497 285 466 288 850 509 737 868 889 36 696 6 863 319 854 797 931 612 670 228 250 137 155 209 543 204 345 135 306 209 277 769 837 37 673 425 909 175 591 209 427 373 600 198 366 181 296 355 723 572 655 30 630 356 388 355 897 403 638 260 905 837 838 41 460 32 345 369 609 463 823 320 337 44 155 303 556 64 726 587 593 498 864 564 623 322 425 366 800 37 88 231 675 216 776 532 705 11 615 111 271 26 826 83 464 130 140 420 915 302 606 254 271 419 505 187 392 228 520 379 920 576 815 448 510 601 728 88 371 518 844 158 615 248 641 316 641 70 816 275 639 450 525 117 753 705 748 207 524 562 567 328 710 344 468 250 875 821 880 299 814 344 512 436 844 268 380 102 320 411 771 98 922 86 468 543 592 186 767 769 787 340 399 857 862 33 899 13 196 434 80…
Output: 6

Example 2:

Input: 1301 1305 1 1301 555 828 102 851 308 1044 165 313 591 852 527 1114 43 438 424 608 22 1190 1060 1105 415 763 760 1003 585 1167 246 402 318 747 859 1024 375 405 270 688 50 1200 1217 1283 716 857 176 1229 371 1165 319 1211 434 1165 664 1175 814 1025 441 817 483 686 379 497 1004 1081 420 851 135 248 734 1021 385 975 58 907 959 1223 935 1228 111 1201 852 1125 564 1211 312 329 524 954 232 563 249 567 429 436 688 1044 962 1234 879 1214 1119 1122 313 605 275 279 494 1230 587 914 312 929 183 678 806 902 390 513 243 1007 701 1278 148 1272 95 154 555 612 349 1032 1139 1144 854 926 281 973 78 815 699 935 137 1013 114 325 1141 1223 931 1079 390 566 435 658 531 972 549 1016 61 342 963 973 887 1089 112 777 541 1065 691 1224 242 765 359 870 1279 1299 507 1154 540 849 222 1165 255 334 667 825 540 678 743 1…
Output: 11

Example 3:

Input: 2719 3781 1 2719 492 2649 167 744 747 850 859 2033 2274 2276 1323 1348 1250 1957 443 2676 1510 1777 1336 1821 328 868 1241 2511 1474 1831 368 1872 272 465 322 1991 601 2029 135 2067 26 2535 4 1136 1156 1825 832 2337 652 1568 1743 1757 1376 2578 1207 2388 707 1197 823 2446 458 2319 1566 2459 212 1813 1929 2663 512 1155 1267 2081 359 1397 947 1823 453 2540 1081 1834 1262 2145 391 2642 447 896 718 1968 169 2191 1126 2319 82 2288 711 2439 62 2666 248 2694 1884 2424 7 276 1149 2275 1535 2224 243 2462 1195 1241 1534 2210 1816 1971 2612 2714 1535 1956 757 897 2262 2353 298 1376 37 2556 70 1041 380 779 136 1328 1124 1331 1423 1647 1205 1977 534 2462 96 164 1417 1422 740 2457 328 1123 1441 2713 223 1790 818 1559 1930 2169 1615 2625 1333 2510 1489 2175 1212 2675 909 2517 158 792 975 979 78 406 665 1…
Output: 7

Constraints:

1 <= n <= 3885; 0 <= m <= 7770.

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