CT29366

Indu's roads Fewest Hops

MediumL4 · Loop LordAcceptance: 0.0%XP: 35

The harbor bell rings at the wren hedges of Thimblewick; Indu weighs the day's roads manifests and starts the calculations. 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 <= 1467; 0 <= m <= 2934.

Example 1:

Input: 1109 1108 1 1109 16 371 436 1033 139 1095 821 822 671 1062 279 479 508 822 486 1036 210 446 132 1102 783 1002 35 596 782 983 505 949 39 954 834 1041 658 839 457 653 208 1002 484 1067 377 957 644 736 310 486 561 758 348 818 789 913 272 298 384 640 501 888 139 288 92 118 217 792 139 221 361 678 541 686 570 1088 20 1056 928 993 250 579 203 453 274 766 103 930 522 897 153 596 685 712 382 932 11 348 1073 1082 172 986 626 918 120 135 340 701 61 294 136 1104 673 860 57 370 895 928 55 865 717 744 1068 1083 249 1006 212 278 340 937 195 982 41 872 31 513 342 671 474 829 98 288 223 401 343 713 463 728 890 1104 393 397 145 1086 40 512 410 861 891 1090 772 976 798 941 282 1062 106 234 692 1051 497 791 137 970 181 864 172 1059 175 982 303 343 280 791 498 1091 176 778 748 1001 510 797 117 137 359 1066 57…
Output: 12

Example 2:

Input: 193 1947 1 193 35 124 33 160 53 85 67 158 66 130 2 34 13 112 81 114 58 84 6 183 89 99 16 102 136 168 1 179 48 118 37 184 11 41 90 93 96 139 14 44 78 136 139 155 74 165 29 117 120 167 29 43 46 54 90 120 101 185 69 113 58 182 130 134 1 71 110 187 160 171 58 77 93 193 28 142 8 155 81 129 49 137 7 177 30 138 48 62 36 41 33 47 133 175 48 155 47 114 121 145 106 152 157 167 89 102 13 84 93 129 64 156 120 162 83 88 84 119 17 181 175 189 80 92 58 148 161 168 110 166 18 23 33 114 10 148 89 121 85 122 1 47 97 141 46 76 57 163 41 60 138 169 69 139 38 79 4 54 12 155 126 151 147 149 32 38 31 104 89 112 147 174 58 73 70 118 91 127 8 40 57 176 29 184 108 164 79 193 1 160 92 100 141 165 83 107 30 188 145 192 108 184 128 132 159 168 65 76 89 163 3 78 90 156 65 75 168 180 95 170 146 182 20 64 51 126 31 110 5…
Output: 3

Example 3:

Input: 1091 1090 1 1091 666 1025 411 487 756 942 219 422 725 1056 821 948 137 878 65 355 414 1043 816 1007 637 1086 31 651 142 1000 612 990 61 65 163 1068 478 910 82 805 340 699 96 474 372 471 55 563 172 1050 424 820 157 623 326 891 35 368 558 896 470 573 819 939 809 872 359 543 372 616 923 981 69 443 537 857 90 233 18 747 616 952 193 377 98 227 142 781 373 421 398 597 810 976 528 1010 850 939 38 142 64 1014 285 890 349 1069 89 709 554 592 503 546 361 501 415 758 588 959 350 641 128 801 240 832 111 974 67 696 170 731 410 591 232 287 153 291 384 614 466 1047 598 925 24 792 56 724 37 47 296 412 136 359 733 920 510 826 303 308 710 911 618 944 666 1003 805 977 515 1062 789 1080 123 333 117 497 178 328 818 834 405 872 428 597 342 867 158 332 135 313 133 157 133 1035 35 753 176 197 581 947 654 1086 80 …
Output: 15

Constraints:

1 <= n <= 1467; 0 <= m <= 2934.

Loading...
Test Cases:No test cases
No test cases available.
Indu's roads Fewest Hops - MEDIUM Coding Problem | CodeTikki