CT39402

The Fewest Hops of the Wistful tunnels

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

At the acacia flats of Thornveld, Zara records each tunnels in a worn leather ledger. The guild wants answers, not guesses. 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 <= 3386; 0 <= m <= 6772.

Example 1:

Input: 1265 5448 1 1265 82 1263 634 822 102 315 491 1242 660 1111 877 1011 818 844 355 1163 755 1001 851 1233 941 954 86 879 199 696 280 564 250 1119 958 1181 495 1218 168 613 1 542 1109 1178 1015 1242 144 1215 327 931 428 590 35 276 184 1196 568 1201 885 1255 93 712 2 35 841 1106 44 782 71 133 148 488 384 1255 532 1106 983 1017 341 507 712 1251 806 953 497 1018 595 988 48 227 28 494 861 1051 49 444 492 1135 475 1251 57 719 65 1130 168 972 309 705 262 650 166 890 983 1252 244 990 575 968 96 471 565 1254 531 715 848 1095 526 670 144 200 343 930 172 392 173 329 391 1249 534 1263 403 483 323 391 394 1142 595 669 884 1229 249 454 874 917 173 1140 408 765 88 152 151 244 77 183 265 747 240 1122 161 194 563 1207 228 735 38 422 449 1004 310 863 303 517 1070 1187 103 208 1017 1216 1055 1167 396 680 574 73…
Output: 3

Example 2:

Input: 1691 5385 1 1691 488 1029 1347 1686 160 1105 614 1025 1051 1254 273 784 900 1580 215 882 736 1239 821 1200 1108 1595 73 770 209 684 768 1028 850 1255 194 285 290 982 334 1383 142 821 255 1356 1140 1250 76 1236 1001 1632 406 696 1448 1669 45 92 4 1254 923 1235 857 1143 155 739 310 541 122 1086 395 1557 554 586 38 1685 1201 1333 1135 1532 212 397 1249 1530 1427 1496 50 1568 870 1499 360 1405 552 1453 294 1507 482 680 713 774 51 97 561 738 99 1319 482 757 101 1505 167 302 169 803 940 1331 1049 1173 474 1298 554 1450 1126 1213 562 1097 159 1244 332 921 251 1592 25 1542 717 1299 361 1577 751 1683 447 843 145 375 440 1578 489 794 396 634 715 741 522 800 498 1311 1290 1391 601 1137 447 1112 491 1025 743 1600 548 1645 162 1445 782 1498 1411 1549 599 1242 1469 1634 564 1290 899 1681 133 1174 434 74…
Output: 4

Example 3:

Input: 1003 6358 1 1003 149 820 845 998 273 368 286 986 64 547 422 1002 163 239 397 484 3 971 333 1002 143 454 459 803 482 937 139 195 264 422 634 877 759 1002 243 757 109 222 19 962 532 656 516 552 282 962 545 810 189 278 655 947 40 161 447 573 536 748 521 681 160 938 453 718 75 396 222 447 538 622 128 940 52 796 597 706 52 239 547 908 165 899 766 786 726 965 839 995 278 727 59 266 22 382 258 297 63 867 167 651 318 360 228 292 473 990 449 571 54 625 302 878 144 1003 4 856 155 264 94 230 153 392 388 434 374 495 28 306 484 697 99 890 134 381 144 440 203 749 174 708 884 890 117 160 347 814 253 902 289 912 123 279 13 922 371 443 87 174 155 252 639 647 192 999 541 660 40 672 542 745 458 820 29 288 63 99 71 252 7 476 368 554 156 983 90 836 953 973 335 610 511 800 557 798 285 342 65 569 88 792 109 952 …
Output: 3

Constraints:

1 <= n <= 3386; 0 <= m <= 6772.

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