CT48081

Ivan Counts the routes

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Ivan runs the ropewalk at the singing sands of Echo Dunes. Today the books show a list of routes, and the numbers must be worked out before sundown. 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 <= 2454; 0 <= m <= 4908.

Example 1:

Input: 992 991 1 992 140 334 757 973 20 596 810 883 807 951 104 271 271 530 408 684 17 925 195 717 647 883 31 256 128 953 428 914 137 580 388 439 583 782 468 615 619 853 83 752 91 278 199 818 111 202 727 971 316 629 21 841 471 910 451 960 527 907 660 734 20 60 364 977 232 831 69 928 259 424 400 930 729 874 736 982 232 618 929 935 206 648 516 786 490 548 98 135 223 894 705 834 30 56 480 599 349 357 303 774 38 917 55 613 503 939 902 934 148 719 36 726 52 145 183 254 637 777 480 962 25 224 158 197 403 866 482 770 132 451 427 506 593 971 485 680 403 669 9 81 500 635 166 892 124 775 386 934 11 687 824 966 498 698 55 747 69 901 365 769 531 752 562 691 420 963 139 761 103 707 686 964 209 681 100 371 217 777 773 922 261 324 26 371 82 462 93 829 111 444 229 792 355 569 176 825 577 796 80 196 397 472 363 9…
Output: 9

Example 2:

Input: 130 1507 1 130 30 78 100 120 3 115 27 121 53 69 7 21 68 82 29 51 92 96 21 66 16 85 29 44 123 129 80 110 11 125 71 95 9 111 81 101 9 100 94 124 14 28 33 37 2 65 40 42 43 102 93 121 25 115 65 110 11 12 31 109 24 77 39 95 1 24 55 61 7 84 90 117 59 124 7 128 92 103 62 106 18 31 88 93 36 48 6 71 23 78 35 129 32 108 25 123 31 38 98 122 22 23 63 70 13 66 40 92 52 55 47 118 105 124 63 78 55 100 4 35 34 122 39 123 19 41 74 88 40 55 4 51 29 67 88 99 36 117 50 82 1 32 33 75 103 104 14 106 25 87 27 116 71 100 19 21 34 53 85 110 4 90 76 117 13 104 22 102 12 118 44 89 11 40 12 106 7 87 108 122 39 65 50 126 65 78 28 81 6 78 44 105 52 74 117 123 17 118 102 130 103 130 18 36 27 61 17 40 70 85 12 60 5 16 23 110 31 80 105 122 16 129 12 64 28 54 81 96 37 122 73 76 48 65 45 101 58 124 73 75 96 124 1 71 31 105 …
Output: 2

Example 3:

Input: 1812 1811 1 1812 1317 1661 258 975 1275 1412 21 504 404 1065 229 1648 520 809 424 1293 333 1507 953 1681 303 433 379 1496 722 736 242 860 547 697 934 966 881 1163 781 1318 112 1741 418 918 1060 1342 258 1350 535 858 783 1269 1480 1769 469 1685 173 875 373 1785 547 626 213 915 348 983 344 657 94 928 1238 1562 373 1714 612 652 493 914 895 1616 1154 1778 959 1431 50 55 84 1801 915 1014 1339 1368 459 1326 325 1026 672 1118 105 319 1145 1539 191 1662 51 1581 559 1141 153 1725 530 1308 145 1306 738 1110 520 1219 543 1165 569 1364 157 675 686 1107 538 790 100 1289 885 1416 209 712 324 436 159 228 1413 1775 546 1060 791 1200 1184 1401 645 917 303 414 837 955 1145 1493 1272 1525 263 1556 721 733 502 1660 650 841 76 1617 1259 1432 712 1084 1133 1507 799 863 302 1655 312 640 1103 1570 448 898 434 115…
Output: 11

Constraints:

1 <= n <= 2454; 0 <= m <= 4908.

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