CT31906

The Gleaming Fewest Hops

MediumL4 · Loop LordAcceptance: 0.0%XP: 35

Quill the cartographer watches over the lantern district of Glowfen's stores of tunnels. A careful computation stands between order and chaos. 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 <= 1669; 0 <= m <= 3338.

Example 1:

Input: 796 795 1 796 259 710 191 277 32 352 279 383 140 781 64 522 74 522 13 318 241 531 4 718 246 683 19 681 238 741 3 379 11 763 12 208 259 789 54 492 115 335 98 321 339 786 183 786 197 429 7 669 472 532 300 368 604 729 177 563 13 40 580 733 46 507 605 782 148 583 19 268 161 595 217 626 49 462 248 331 352 577 562 618 174 303 341 446 319 658 400 782 179 354 150 243 322 457 6 587 43 555 555 783 19 473 634 647 182 399 508 755 651 655 161 584 99 297 258 268 291 365 265 597 109 303 407 451 620 644 11 205 242 247 508 700 559 773 193 449 163 612 45 527 419 510 381 562 126 533 166 349 188 564 222 712 46 293 29 598 57 478 87 215 203 500 473 597 356 699 34 84 678 718 360 741 100 197 385 440 397 640 261 460 55 399 320 721 163 324 761 774 335 571 152 618 112 519 175 443 581 746 48 630 323 457 48 462 215 74…
Output: 18

Example 2:

Input: 42 861 1 42 13 34 1 27 11 35 9 33 8 26 27 36 19 27 6 34 7 37 26 39 7 21 14 38 41 42 3 34 10 33 6 11 20 34 27 29 17 20 4 28 9 17 26 40 26 35 7 12 6 42 2 8 19 31 15 27 31 37 1 25 21 33 23 26 8 29 7 29 3 37 3 4 24 29 3 16 2 36 5 8 5 23 16 29 28 41 19 22 10 32 12 42 7 33 31 32 13 32 10 15 12 20 4 37 21 29 16 30 10 36 21 24 35 36 17 22 7 17 32 38 13 29 3 14 36 40 9 35 4 12 17 23 16 27 2 16 9 41 18 20 11 30 8 9 4 16 17 42 4 42 11 40 6 16 17 39 26 30 1 36 21 40 1 7 5 12 19 30 11 29 12 35 22 34 15 25 2 33 15 30 38 40 1 33 7 35 10 12 15 22 12 33 24 42 31 35 9 18 21 42 5 10 24 34 23 32 33 37 1 3 14 28 15 19 5 36 12 27 10 29 13 36 25 33 3 9 12 22 22 41 24 30 27 34 10 16 2 37 3 8 14 33 33 35 31 36 8 19 9 28 12 13 11 31 6 33 2 20 1 35 1 18 3 21 14 25 3 32 25 39 29 31 2 31 15 29 28 30 5 29 14 26 2 14 13…
Output: 1

Example 3:

Input: 1320 1319 1 1320 513 1302 105 976 1137 1288 562 624 680 813 393 516 136 641 1175 1251 18 967 665 1303 752 962 261 951 11 556 706 1141 666 696 745 840 541 935 719 901 110 1147 46 132 356 744 158 952 349 393 47 212 650 836 195 935 106 682 439 1217 1047 1217 427 1034 45 1110 289 765 438 479 63 1011 21 938 257 609 114 993 454 848 526 1088 881 948 718 1021 180 991 300 1043 321 1041 1 902 472 911 878 1210 387 1227 193 656 442 762 722 1139 737 897 775 980 426 675 495 654 1216 1262 330 377 257 698 142 795 748 1280 92 917 21 36 152 537 197 776 233 1269 317 793 428 1277 531 1164 548 1076 397 1226 142 408 513 1209 453 718 155 527 638 804 21 1275 218 444 899 1013 670 1185 37 577 410 424 17 584 73 516 464 534 794 1195 354 946 248 628 13 107 215 738 292 702 137 624 54 872 715 1047 174 312 996 1167 527 1…
Output: 11

Constraints:

1 <= n <= 1669; 0 <= m <= 3338.

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