CT35192

Tina Counts the corridors

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Legend says the vault under the spice bazaar of Saffronia opens only for a perfect tally of corridors. Tina means to find out. 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 <= 3264; 0 <= m <= 6528.

Example 1:

Input: 1210 5760 1 1210 312 1123 206 1071 921 1134 1 321 713 883 866 986 313 1006 236 1141 1109 1176 370 840 47 724 310 813 71 132 61 445 493 688 450 539 53 205 593 892 838 1146 389 714 668 932 73 1139 1023 1036 140 648 413 442 105 179 62 1085 356 532 439 590 111 1075 41 631 7 706 126 805 122 602 691 852 214 614 655 1117 39 131 205 340 828 1181 374 805 696 984 248 781 300 410 188 731 713 861 594 1095 717 1015 83 1107 327 511 192 555 190 998 98 821 429 1199 741 875 488 1143 689 976 443 809 286 663 556 689 128 707 200 427 326 444 371 428 338 833 150 1126 14 454 174 901 31 971 46 835 377 761 734 791 310 736 419 1206 121 1199 34 1208 363 732 115 995 702 1037 259 758 690 1024 61 732 525 1175 614 1023 454 661 9 1171 228 939 393 1182 143 857 683 1026 102 731 1018 1115 186 622 227 688 91 384 445 1071 435…
Output: 4

Example 2:

Input: 927 2603 1 927 356 649 109 708 332 422 27 412 647 818 352 759 154 727 41 316 549 803 512 763 148 438 132 416 473 676 29 709 33 571 674 747 484 773 642 735 105 155 752 814 311 378 443 777 235 705 26 760 47 128 193 256 305 614 7 204 532 711 116 399 547 643 661 751 706 741 456 694 391 691 282 543 320 535 651 668 458 904 706 827 46 411 452 734 184 752 348 834 483 683 52 426 85 126 75 679 903 911 114 467 227 432 63 432 218 220 236 498 79 279 186 216 159 891 361 511 55 816 132 722 313 722 306 380 468 710 75 116 253 601 140 768 162 434 401 446 333 859 523 859 498 904 116 793 221 618 353 722 390 489 533 715 3 235 528 575 379 845 375 466 627 647 195 688 448 639 479 900 364 904 67 436 83 386 36 457 432 860 321 379 720 877 312 801 138 496 612 906 84 600 93 418 912 920 321 767 195 910 522 820 856 911 …
Output: 3

Example 3:

Input: 2400 5651 1 2400 1201 2166 1715 2130 327 532 706 1426 106 2266 146 1997 313 907 1690 1803 1372 2248 398 2211 2153 2266 1520 2314 504 528 1162 1514 1852 1889 14 65 188 1597 181 255 2043 2395 1028 1139 610 2255 1543 2360 426 1041 1736 2223 1645 2393 370 589 1062 1470 162 2165 146 1059 589 2354 77 2178 1556 1725 268 475 419 1528 77 1887 159 978 1351 1734 1444 1844 444 2223 2058 2296 1766 2054 765 794 547 551 431 1283 306 622 1243 2192 54 2033 425 2034 92 1793 635 1544 1840 1903 106 357 954 2035 506 1813 632 2377 192 1434 293 972 390 1046 154 1863 40 1621 1796 2277 1388 1704 1177 1723 873 2315 324 1277 429 956 872 2252 1153 1602 1053 1594 1542 2172 1413 1882 1262 1446 557 1120 1330 1940 434 655 386 2399 1242 2279 41 465 1475 1769 1296 1768 938 2111 35 1605 378 1834 1077 1911 1895 2105 588 1939…
Output: 5

Constraints:

1 <= n <= 3264; 0 <= m <= 6528.

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