CT32001

Gautam Counts the bridges

MediumL4 · Loop LordAcceptance: 0.0%XP: 35

Morning light hits the orchard lands of Applerun as Gautam unrolls the day's manifest of bridges. The tally will decide the next shipment. 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 <= 1493; 0 <= m <= 2986.

Example 1:

Input: 1470 1499 1 1470 827 1197 228 331 69 1031 440 1223 438 844 196 1161 752 1420 1182 1422 3 1188 1141 1393 245 519 1165 1387 1172 1260 66 458 150 931 1 923 1 463 605 1257 1079 1116 1003 1322 10 536 1087 1416 228 1151 924 1378 278 772 548 563 424 948 98 563 1007 1163 445 1232 166 782 26 689 31 628 255 687 169 572 359 400 342 1245 792 1356 209 567 706 1157 600 670 362 1185 174 549 506 1408 647 709 809 1375 807 1261 773 1265 598 1343 314 708 948 1212 220 1357 577 690 505 1041 911 1258 695 793 952 1185 433 925 989 1025 34 1104 952 1092 534 1466 352 1106 190 450 123 1142 516 696 140 1081 626 866 615 799 55 1060 407 743 477 1402 471 911 265 656 70 250 170 1230 618 906 249 811 162 733 537 1289 113 1405 734 1092 1121 1268 522 678 585 816 59 1263 181 634 422 445 872 1200 793 1170 411 890 345 1413 91 8…
Output: 8

Example 2:

Input: 1444 2637 1 1444 678 1078 121 742 143 353 245 1002 964 1207 532 770 286 1280 104 803 15 603 4 474 602 1298 699 883 516 561 97 175 961 1409 712 830 65 1129 857 1159 83 1266 60 816 777 1184 56 497 425 898 151 764 402 579 374 388 575 1404 60 905 428 601 612 936 640 1404 529 849 369 874 386 1393 67 157 1324 1327 754 1189 994 1412 539 1119 643 1398 1014 1137 501 695 802 1293 599 1145 646 1159 349 565 375 496 489 1248 896 1161 226 749 26 294 1071 1213 947 1246 671 845 80 992 388 942 500 1304 826 1189 447 876 739 1196 893 1231 1172 1437 640 815 255 545 519 1128 701 1065 632 943 137 582 830 1270 321 1432 456 658 1091 1297 293 943 1313 1370 307 1178 885 977 253 641 65 673 217 873 984 1325 7 1017 201 881 787 861 570 1187 416 868 664 711 297 341 1020 1302 218 421 26 361 662 1256 103 247 610 1140 643 …
Output: 6

Example 3:

Input: 1121 2129 1 1121 312 930 477 1043 864 1045 46 149 9 662 49 153 99 228 691 766 263 716 64 988 14 707 97 1076 258 668 711 950 457 1066 192 280 107 727 945 1068 976 1030 430 753 109 891 141 156 611 853 131 709 343 374 141 797 309 802 396 981 93 554 823 874 110 574 432 1088 87 638 392 880 912 995 936 1094 65 1055 141 862 443 864 275 1108 366 644 65 992 193 1101 66 695 511 893 497 1118 98 510 117 622 347 452 641 898 177 205 178 1034 183 789 88 141 191 1028 138 617 717 765 260 949 124 397 483 778 398 882 763 1048 609 818 702 779 4 142 583 966 481 1015 537 580 256 512 157 378 371 411 99 462 784 1044 52 57 270 984 59 696 615 962 911 980 157 783 656 1004 499 1068 851 870 204 282 912 1047 250 604 97 933 568 647 554 1063 576 830 174 426 84 600 116 589 34 463 763 1021 385 557 47 675 301 434 785 1034 1…
Output: 5

Constraints:

1 <= n <= 1493; 0 <= m <= 2986.

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