CT42680

The Azure Fewest Hops

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Caravans arrive at the copper works of Verdigris with crates of canals, and Dorian the customs officer must account for every last one. 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 <= 2065; 0 <= m <= 4130.

Example 1:

Input: 1072 3623 1 1072 593 1032 323 766 679 712 155 537 498 812 876 888 730 830 880 1060 197 944 605 875 644 989 17 218 327 354 31 546 413 825 201 737 136 649 200 696 774 933 114 269 148 913 959 1058 494 778 453 574 386 507 75 1008 187 742 327 448 674 676 4 864 295 520 472 795 505 688 268 924 451 723 245 1069 207 738 110 565 880 930 51 941 403 481 11 662 335 571 441 851 77 671 840 971 434 991 498 522 165 757 570 690 241 447 90 216 376 581 93 277 269 780 175 695 325 826 939 966 452 937 68 339 569 640 161 918 446 480 8 869 693 779 497 606 157 365 65 572 666 903 1047 1062 452 952 489 753 148 678 152 852 373 1026 625 804 364 906 745 773 574 900 211 465 75 181 669 915 873 970 23 312 846 1054 544 591 245 859 221 318 303 662 118 476 86 551 76 1023 48 915 776 826 268 776 442 848 17 704 548 1024 48 755 3…
Output: 4

Example 2:

Input: 1827 3897 1 1827 194 1691 116 785 1057 1437 494 1155 847 1524 1094 1436 15 452 1220 1418 766 954 591 1155 110 1270 359 810 745 1093 814 1283 200 732 92 908 477 1307 771 1398 1175 1615 200 1017 242 681 1012 1368 53 935 25 638 28 1081 453 1014 19 1101 596 922 298 366 594 626 1289 1459 1004 1818 480 524 113 983 337 1695 1491 1769 297 928 238 1587 278 1572 953 1254 1219 1470 749 1778 318 728 90 1002 1335 1592 953 1114 885 1625 696 866 1065 1516 330 672 570 1301 395 1762 390 1556 349 490 461 774 329 1744 844 965 675 1730 707 889 561 997 1159 1173 441 1216 458 832 830 1393 373 438 245 1539 83 297 1314 1325 292 910 809 1071 983 1632 201 1062 9 891 53 100 807 1344 583 1010 998 1587 535 620 267 301 964 1421 523 1267 1635 1825 1068 1740 870 1815 747 803 280 574 790 1358 1158 1188 1008 1754 757 1327 …
Output: 5

Example 3:

Input: 1117 1116 1 1117 805 1004 80 422 805 869 472 625 100 1054 363 589 139 323 491 680 414 424 359 719 134 667 187 312 86 436 3 162 68 777 86 315 178 958 663 749 328 773 144 476 456 742 400 456 285 838 139 738 129 518 78 641 753 1084 404 667 89 188 42 473 944 1082 210 654 516 674 246 636 403 563 811 967 2 52 301 436 146 928 101 457 85 795 864 1068 1000 1014 282 1025 98 695 843 939 784 971 802 1114 132 771 164 667 402 1006 236 955 1069 1094 152 1101 46 245 473 1049 446 1005 4 259 1 278 476 955 221 333 394 446 432 720 108 484 49 1021 51 1091 798 886 130 363 345 978 96 729 333 856 281 681 272 1108 677 790 826 894 243 291 239 319 124 917 30 933 390 953 73 992 320 1082 982 1067 269 507 120 412 899 1027 33 1085 688 748 272 407 159 784 183 485 795 965 14 494 342 1072 474 713 240 488 973 1051 573 708 6…
Output: 13

Constraints:

1 <= n <= 2065; 0 <= m <= 4130.

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