CT43690

The Coralcove Fewest Hops

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Wren found an old ledger of corridors in the lighthouse attic at the island market of Coralcove. The margin notes pose a precise question. 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 <= 3049; 0 <= m <= 6098.

Example 1:

Input: 11 55 1 11 8 9 4 9 3 4 10 11 5 6 9 10 1 9 1 11 2 6 5 9 2 10 4 5 5 7 3 11 9 11 4 7 4 10 6 9 4 11 1 4 1 3 8 10 3 9 2 5 6 11 3 10 5 11 3 8 1 8 2 9 3 7 1 2 3 6 5 10 7 9 6 8 4 6 7 11 4 8 1 7 1 10 6 7 3 5 2 7 1 6 2 3 5 8 2 4 2 8 7 8 7 10 8 11 1 5 6 10 2 11
Output: 1

Example 2:

Input: 1396 4901 1 1396 1139 1321 874 1378 603 1272 121 975 1127 1257 328 457 249 1373 773 1003 41 1074 235 1296 436 1359 656 1387 100 202 28 214 133 538 762 1316 175 1126 802 1272 704 999 262 1310 470 1360 437 698 429 1093 1093 1295 370 783 93 313 690 1141 660 904 60 539 1108 1372 748 817 873 1142 349 436 124 335 380 692 1012 1077 688 1330 1078 1294 134 858 205 1118 286 1260 524 649 89 422 121 1014 671 813 534 844 70 1297 180 1302 160 755 273 277 389 1001 116 812 813 1337 108 209 643 1345 533 1313 102 579 123 396 1085 1155 457 903 449 727 61 908 339 1289 378 447 886 1010 662 1340 599 1319 749 1362 1085 1171 349 1304 599 1370 127 153 239 338 661 1164 711 1011 376 510 871 1357 420 1068 707 1159 223 1036 598 810 187 918 720 758 481 695 609 967 513 968 536 854 1081 1218 311 1251 272 777 70 762 607 9…
Output: 2

Example 3:

Input: 892 891 1 892 691 861 218 323 45 48 196 234 290 391 80 84 108 880 364 684 517 574 172 413 129 813 152 361 686 818 445 717 220 607 680 684 388 667 300 683 460 611 89 93 685 807 354 510 57 843 607 739 75 836 30 430 229 231 175 248 10 270 540 697 17 602 175 764 215 284 805 884 469 860 202 511 719 808 30 680 189 434 7 845 449 452 114 716 255 338 204 302 179 797 142 740 84 458 626 887 538 558 272 469 558 781 390 545 145 826 1 69 26 225 297 630 287 523 104 698 286 472 502 848 526 551 174 290 159 658 187 306 466 618 775 853 10 62 15 357 30 262 301 475 152 573 521 834 590 844 115 206 337 654 391 885 112 334 19 811 680 839 445 837 551 764 43 385 533 592 123 137 161 602 70 562 119 565 227 853 253 599 173 740 149 740 360 825 27 721 675 864 21 392 70 311 310 631 379 539 607 758 318 750 78 866 242 765 …
Output: 13

Constraints:

1 <= n <= 3049; 0 <= m <= 6098.

Loading...
Test Cases:No test cases
No test cases available.
The Coralcove Fewest Hops - MEDIUM Coding Problem | CodeTikki