CT31545

The Polished bridges of Cartwright

MediumL4 · Loop LordAcceptance: 0.0%XP: 35

Cartwright inherited the archive at the maple sugarbush of Saprun along with its curious bookkeeping system for bridges. Time to make sense of it. 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 <= 1339; 0 <= m <= 2678.

Example 1:

Input: 1007 1862 1 1007 29 485 17 298 335 375 645 1006 251 348 128 359 331 659 889 1005 226 987 489 568 675 906 225 543 283 461 86 224 460 949 54 664 609 648 246 915 160 209 470 730 315 600 2 327 91 407 338 505 401 618 486 825 150 768 224 268 546 831 319 843 99 771 287 715 516 715 732 836 259 514 878 897 176 340 475 1007 155 595 437 954 189 631 656 730 245 684 133 766 3 948 47 907 350 738 288 626 30 587 324 616 167 312 233 382 581 869 219 342 149 239 642 752 6 353 35 824 288 756 155 513 6 202 536 900 137 895 149 838 680 877 225 988 365 521 727 784 98 250 18 156 838 979 101 155 519 733 95 823 437 992 79 657 176 879 843 869 48 720 306 851 326 828 704 951 586 649 260 742 605 927 264 788 538 930 282 662 204 858 46 894 229 983 508 852 859 995 70 391 240 282 53 565 163 874 348 627 232 587 235 373 126 1…
Output: 4

Example 2:

Input: 994 2260 1 994 252 624 313 766 651 918 164 577 168 536 25 336 76 445 176 785 515 639 379 692 22 615 257 606 141 682 650 955 410 957 559 930 101 411 108 790 477 671 2 811 626 673 844 882 68 683 285 625 343 412 21 426 489 694 287 585 635 675 51 147 650 887 22 120 63 816 191 617 84 442 292 819 41 331 86 908 864 939 201 808 65 497 464 742 716 955 352 642 640 769 42 365 353 681 270 482 113 286 485 697 89 529 390 775 353 769 276 758 193 812 299 539 441 501 5 852 177 352 200 693 83 860 90 790 749 814 242 453 218 414 146 339 60 598 3 255 111 424 568 724 895 994 38 156 474 898 225 583 106 456 744 770 33 243 78 131 938 967 9 280 355 607 47 269 120 372 268 326 478 774 232 504 25 96 396 803 420 884 242 962 405 613 270 314 44 310 428 692 172 898 640 932 279 769 733 815 877 932 7 650 224 242 100 298 738…
Output: 5

Example 3:

Input: 1303 2539 1 1303 1 358 688 1225 277 998 64 1023 1231 1243 515 1177 487 1155 51 130 903 1250 709 1130 259 487 30 997 497 636 75 552 42 986 603 1181 552 1243 220 910 142 529 519 792 151 1099 284 824 745 822 935 1220 538 1122 186 230 1086 1262 797 1028 181 321 675 856 384 1287 788 1092 129 385 295 1026 538 856 537 673 142 218 646 983 858 1234 278 465 198 483 798 1276 89 1061 129 949 820 1129 1021 1158 142 404 67 1205 548 1049 79 1135 373 591 33 373 600 1251 1158 1300 552 1037 581 598 142 1002 11 148 274 926 355 841 992 1147 74 451 418 1301 745 1242 773 982 657 873 181 1097 314 831 681 806 122 151 79 226 957 973 612 999 315 627 541 811 1096 1211 344 1226 327 1103 302 355 330 473 199 989 568 1224 816 1002 416 681 854 1150 55 1098 231 914 573 953 412 1246 710 1110 304 669 194 1159 395 1038 254 1…
Output: 4

Constraints:

1 <= n <= 1339; 0 <= m <= 2678.

Loading...
Test Cases:No test cases
No test cases available.
The Polished bridges of Cartwright - MEDIUM Coding Problem | CodeTikki