CT41274

The Fewest Hops of the Golden roads

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

The council of the fen lights of Will-o-Wisp pays by the answer, and Tanya intends to earn it. First: the full register of roads. 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 <= 1912; 0 <= m <= 3824.

Example 1:

Input: 970 3521 1 970 562 921 394 833 506 955 266 280 99 408 387 398 558 849 189 752 641 776 19 144 382 899 508 831 59 653 245 617 395 716 241 637 620 738 71 266 559 870 19 183 228 326 33 783 278 312 88 112 6 381 546 674 124 253 8 565 537 632 52 150 23 510 520 950 378 726 343 528 240 782 432 749 152 883 159 636 17 720 377 891 125 472 112 167 20 136 54 307 154 486 723 888 14 961 323 389 41 338 214 495 9 574 729 862 175 822 59 364 778 880 473 480 472 911 510 779 142 173 365 665 675 714 515 689 550 639 380 894 85 908 653 681 128 217 89 243 191 461 88 817 239 582 87 578 154 902 120 616 88 233 156 908 393 915 162 793 106 639 85 133 250 291 864 872 451 969 575 627 152 603 699 703 64 846 326 444 164 421 375 905 849 893 471 710 362 792 31 246 194 661 22 154 90 370 200 768 42 289 101 155 101 916 141 719 2…
Output: 5

Example 2:

Input: 1553 2813 1 1553 1171 1241 52 741 150 507 100 488 434 1111 283 587 1021 1155 196 306 313 1337 114 719 428 873 612 1070 659 1544 227 753 237 1520 132 431 303 791 874 1096 695 1032 398 1506 1177 1530 314 432 576 872 220 331 348 1373 606 1023 712 1091 487 1112 639 1067 355 970 924 1133 952 1365 309 1188 387 701 34 618 19 369 1031 1146 192 334 702 801 246 1101 512 756 990 1090 1449 1461 582 841 53 1003 349 1134 611 969 222 958 153 218 714 1043 8 1501 743 1534 506 1327 338 481 985 1535 8 865 1100 1171 987 1214 423 487 409 595 272 656 353 841 81 255 966 1408 607 1211 1033 1207 838 1397 105 693 381 884 458 989 812 1050 559 1212 569 694 137 951 132 1481 32 1479 931 1501 84 1424 1492 1512 232 434 825 1103 325 1133 931 1255 258 1540 633 647 630 1444 871 1478 14 480 1072 1166 716 897 884 910 734 968 …
Output: 6

Example 3:

Input: 1833 3628 1 1833 988 1082 1619 1792 212 894 353 614 1087 1453 1452 1484 1161 1206 58 1237 1090 1798 302 1622 1001 1580 59 369 813 872 209 260 725 732 779 820 12 52 744 1828 815 1099 445 1651 177 363 374 544 864 1149 369 408 1358 1658 75 270 1606 1716 66 767 1719 1786 303 1650 319 1304 359 736 761 1342 265 1005 1239 1337 685 1559 83 1226 338 1007 297 776 265 628 530 1169 643 837 792 1554 504 1164 1428 1537 67 1090 1241 1761 340 1456 851 1300 366 1318 485 1762 1185 1436 420 1633 1011 1260 843 1131 248 438 585 1057 1424 1691 1299 1619 356 1074 171 1755 609 1012 1538 1659 1012 1608 768 1104 1158 1263 161 893 576 1206 1696 1729 62 1004 193 1600 968 1753 109 827 290 403 1204 1699 873 1476 226 1303 286 439 1196 1760 855 1560 171 1469 554 1240 838 1139 452 589 620 1427 1255 1724 1260 1555 187 256 …
Output: 5

Constraints:

1 <= n <= 1912; 0 <= m <= 3824.

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