CT53557

Mina's Fewest Hops Ledger

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Mina found an old ledger of canals in the cooperage attic at the obsidian flows of Blackglass. 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 <= 3213; 0 <= m <= 6426.

Example 1:

Input: 686 6081 1 686 59 523 216 675 195 258 487 581 212 510 593 675 331 665 57 534 271 440 316 509 275 483 415 659 88 495 7 147 384 649 11 367 382 566 329 393 649 673 162 483 51 79 367 489 118 390 84 302 165 349 290 400 285 362 9 681 185 603 299 395 299 425 244 412 221 258 420 585 91 595 310 670 308 464 338 361 70 378 169 545 229 504 31 591 77 434 119 196 70 409 62 262 481 643 134 142 145 528 368 619 330 454 523 614 467 658 77 591 404 626 234 260 226 471 14 531 389 405 419 552 312 677 648 678 24 30 496 571 310 549 488 659 426 467 106 595 349 474 323 342 173 493 385 681 398 459 1 670 416 615 349 525 15 111 261 499 197 572 97 257 590 635 78 465 90 285 309 316 176 220 95 420 268 644 78 349 197 381 109 350 401 590 54 559 296 660 42 581 3 645 504 603 247 655 15 492 237 435 27 331 17 113 209 478 474 6…
Output: 2

Example 2:

Input: 3167 4912 1 3167 339 845 1229 1428 463 2848 210 343 152 1302 1218 1910 197 1177 1119 1202 667 2675 458 842 575 1193 163 1851 1028 2760 2449 2572 527 3114 1126 2408 42 2919 366 963 359 782 1497 3085 2046 2383 929 2158 2420 2642 268 1084 599 1249 2306 2782 269 2775 1044 1439 1711 2620 335 1049 1313 1872 2465 2689 1446 1508 294 2488 450 3043 2721 3007 112 1399 522 545 801 2163 1387 2851 41 2585 1027 1547 1806 2058 322 1454 956 1759 1263 2592 1314 1862 721 1258 373 2146 175 452 1263 3112 446 1016 370 2043 1196 1629 1483 1897 955 1294 1567 2055 2194 2984 556 1450 1858 2354 800 2182 1856 2164 1479 2514 988 2010 1788 3114 1933 2757 2260 2416 1454 2692 278 980 907 2779 1666 2412 988 1358 1406 2178 964 2660 805 1917 421 910 448 1602 121 238 281 1001 1926 1998 543 2974 416 2092 1053 3139 1048 3000 9…
Output: 8

Example 3:

Input: 985 1824 1 985 662 753 298 748 342 758 226 805 728 956 660 698 403 804 99 624 237 519 80 190 572 591 114 560 191 866 831 930 264 666 248 706 283 332 202 746 541 637 59 365 159 625 74 849 632 945 198 930 416 553 207 836 488 562 272 526 116 705 154 206 90 693 501 892 457 860 881 936 514 534 131 889 316 318 477 857 246 412 133 504 529 640 269 412 200 631 52 693 185 311 539 549 87 777 529 808 73 390 299 591 646 869 7 662 325 798 11 837 248 957 69 108 159 710 468 727 768 946 426 946 688 946 230 955 218 258 228 866 214 798 483 721 734 976 179 891 470 729 764 801 76 930 179 375 214 659 3 440 362 924 127 199 365 519 624 694 893 901 17 632 821 872 16 343 2 565 364 869 254 494 100 854 303 628 540 633 238 495 187 975 17 44 649 770 4 316 529 831 257 454 234 324 399 550 67 767 862 867 13 296 22 446 796…
Output: 6

Constraints:

1 <= n <= 3213; 0 <= m <= 6426.

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