CT37145

The Fewest Hops at Horselord Plains

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Every season at the steppe camp of Horselord Plains, someone must track down a clerical error. This year the task falls to Anaya, armed only with the bridges register. 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 <= 1857; 0 <= m <= 3714.

Example 1:

Input: 1463 1462 1 1463 776 1008 181 762 1174 1224 1123 1128 140 1434 1348 1351 147 236 393 1324 479 803 491 1041 158 614 722 1280 455 1017 159 1186 135 875 159 1337 291 424 186 1369 526 631 39 1080 912 918 873 931 195 1172 449 769 725 1276 221 1150 325 500 417 990 699 1366 768 787 755 1138 160 1362 976 1094 241 1050 542 1060 836 1344 825 1253 1 42 600 1103 650 1078 412 604 112 1300 627 1120 239 883 593 921 64 1414 229 699 510 1407 210 1428 784 1299 60 523 1160 1288 426 843 125 1200 1058 1425 1114 1149 94 971 91 248 571 1321 431 1195 181 526 365 414 778 1124 184 665 740 1370 466 1409 620 880 119 172 976 1137 343 446 226 378 59 1144 22 686 682 1085 156 1424 50 89 781 1387 982 1016 156 803 31 256 477 1084 448 492 37 1437 756 768 639 1301 63 381 182 324 1309 1424 369 1058 608 1230 544 1244 1201 1275…
Output: 20

Example 2:

Input: 1355 1354 1 1355 90 628 11 388 576 1271 850 1147 835 1073 249 477 526 1104 173 1183 219 1197 417 836 477 873 895 1070 123 1290 420 673 203 1037 555 837 273 843 676 788 243 655 683 1272 639 924 786 832 517 672 345 450 795 905 824 934 583 724 230 1090 152 974 1152 1265 145 303 121 1322 415 1255 982 1311 458 1146 164 1225 158 340 565 1137 130 1043 722 1081 842 1062 1011 1302 146 586 142 1173 735 1197 121 534 228 975 104 1070 987 1206 811 891 534 1323 271 337 260 840 226 590 799 1290 144 1085 454 1292 163 1070 781 1137 154 959 476 1174 659 692 855 1250 910 1143 296 1310 816 1290 520 1293 52 272 29 1272 186 477 164 1171 242 954 466 916 365 1026 339 759 721 848 91 705 461 741 641 664 743 928 688 704 115 893 124 491 313 1282 427 675 334 835 712 1015 531 1198 218 1076 366 836 755 859 798 962 62 23…
Output: 17

Example 3:

Input: 1255 2350 1 1255 893 1221 731 931 710 762 241 1014 487 734 571 678 716 1185 171 1207 218 583 254 279 450 626 259 882 40 268 793 957 1007 1203 454 1012 87 778 448 1176 255 1011 58 1218 268 695 524 696 625 1005 441 1180 26 735 340 708 660 783 91 1151 941 1163 234 1158 89 1205 456 641 477 1163 151 163 237 640 138 1237 415 995 449 1050 9 818 1080 1182 1017 1029 271 442 641 1061 204 760 636 984 236 567 43 924 28 210 625 922 633 711 183 272 238 1010 832 1129 444 539 221 1195 176 1221 1003 1224 716 1117 452 674 165 166 44 928 337 520 441 810 12 824 43 205 272 761 65 776 310 789 573 923 55 399 277 887 342 715 46 404 19 890 234 1253 341 876 348 1130 395 611 110 288 821 1019 302 1099 38 722 514 1233 403 620 210 335 189 745 386 791 456 829 161 749 512 1028 586 687 544 721 148 495 113 273 259 866 272 …
Output: 6

Constraints:

1 <= n <= 1857; 0 <= m <= 3714.

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