CT48705

Mossy canals Fewest Hops

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

The cartographer Chandler has been asked to forecast next month's demand. On the desk lies a long table of canals readings. 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 <= 3417; 0 <= m <= 6834.

Example 1:

Input: 1094 1093 1 1094 19 309 883 933 238 402 230 622 867 1038 451 896 303 471 226 306 170 954 730 866 143 826 207 964 37 614 303 731 214 257 21 67 543 544 499 746 277 677 120 354 351 438 60 568 475 1034 61 299 533 1007 450 1029 29 649 190 660 549 1035 106 161 436 867 268 341 114 848 316 962 550 812 107 958 43 554 287 449 36 154 383 844 209 265 664 672 214 218 38 1094 299 485 38 318 762 878 333 602 411 724 592 1052 241 652 418 1042 412 1007 472 592 939 947 111 162 45 466 626 629 18 368 261 392 185 550 174 536 495 971 436 823 429 958 125 310 256 667 126 418 900 979 222 303 955 1055 416 1053 621 887 6 345 466 532 259 729 155 682 30 939 342 995 584 953 165 263 840 950 319 507 185 250 575 844 55 890 396 1081 330 949 260 436 162 739 280 966 81 1014 475 723 109 530 128 484 878 1043 279 718 509 921 662…
Output: 13

Example 2:

Input: 819 3207 1 819 32 624 288 327 175 439 192 613 37 99 200 225 204 579 94 232 604 700 9 582 212 249 455 718 65 740 60 345 421 638 537 804 192 443 351 535 6 221 509 530 125 283 119 800 72 290 40 565 146 320 91 480 27 432 32 422 258 268 507 629 476 577 226 294 189 392 46 591 206 494 517 791 629 721 270 302 452 603 364 798 41 745 101 803 525 762 101 780 285 746 150 347 606 746 642 741 178 786 416 425 233 583 380 487 60 363 333 379 258 770 299 787 402 501 570 806 64 786 637 650 807 808 263 270 113 544 352 369 531 584 443 475 407 415 129 158 558 813 311 403 434 791 322 353 195 699 181 813 154 346 288 541 538 775 28 574 81 713 538 589 480 799 612 681 299 739 91 786 57 291 211 451 380 461 406 549 79 363 445 679 318 699 118 306 57 323 260 472 571 737 125 420 357 531 324 385 619 657 240 489 360 430 13…
Output: 3

Example 3:

Input: 154 6394 1 154 65 98 41 72 68 114 67 95 49 106 88 122 96 137 10 113 18 77 45 71 67 153 104 147 15 135 9 144 64 104 58 130 37 51 20 105 50 133 70 79 27 115 14 31 53 152 54 80 93 95 9 32 35 60 45 59 55 84 88 94 104 134 29 32 72 146 59 77 2 65 36 44 5 149 22 93 99 122 41 148 50 62 72 117 95 135 51 95 14 29 52 83 41 115 99 134 29 81 31 107 21 147 37 80 64 91 96 129 8 144 20 35 57 68 34 80 106 111 15 71 32 40 1 104 78 151 118 146 63 67 88 141 102 154 4 99 90 148 5 12 15 32 3 92 100 137 34 53 49 149 68 99 21 40 78 80 35 140 40 114 23 109 2 56 27 117 34 138 85 128 28 57 1 127 29 79 19 136 83 105 15 131 55 108 14 141 12 26 50 117 14 111 94 144 21 117 16 63 107 149 24 87 25 125 44 47 46 82 46 142 37 67 22 76 19 142 55 141 68 123 109 147 93 112 47 130 42 126 59 107 7 124 41 66 30 133 63 124 102 113 …
Output: 2

Constraints:

1 <= n <= 3417; 0 <= m <= 6834.

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