CT42970

Freya and the Fewest Hops

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Deep in the seal rocks of Barking Cove, Freya studies rows of routes entries. One clean number will settle the guild's oldest argument. 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 <= 3521; 0 <= m <= 7042.

Example 1:

Input: 724 5905 1 724 498 614 335 411 337 594 486 601 538 667 16 247 393 561 347 684 78 535 176 505 40 488 196 413 259 346 289 342 511 724 579 706 44 611 9 227 292 449 31 398 293 722 18 648 441 482 39 281 438 459 425 562 19 488 566 611 198 248 19 704 305 415 141 384 530 579 292 492 196 327 357 507 273 326 124 329 665 681 272 600 178 309 60 490 301 437 56 470 132 383 302 420 202 581 629 683 252 314 72 286 74 138 241 632 41 537 233 532 256 334 31 135 169 363 10 704 247 586 263 684 17 511 141 577 241 588 300 695 306 532 108 396 252 638 282 442 374 503 267 476 43 430 130 420 306 496 317 378 80 694 299 633 167 518 196 425 420 700 127 700 60 503 103 126 326 643 223 383 264 471 184 602 449 678 349 505 19 454 114 255 44 203 40 447 42 183 6 408 627 707 129 680 412 469 109 318 229 682 63 459 57 103 56 274 …
Output: 2

Example 2:

Input: 2006 2005 1 2006 447 1185 125 492 848 1857 287 613 212 476 1075 1943 728 1535 662 1194 759 1575 244 1376 346 1794 202 767 47 1921 762 1537 894 1663 1322 1766 38 1513 603 1234 580 1266 699 1551 869 1482 192 897 172 733 332 1380 1309 1750 445 898 257 320 885 1515 1043 1303 143 1810 1406 1678 331 685 618 621 249 1027 516 1977 891 1045 743 1008 427 794 229 880 524 1665 1126 1304 1681 1999 1540 1921 763 1171 95 1618 324 785 1563 1755 499 2002 1262 1644 1231 1928 40 1976 8 1949 1094 1617 222 1312 263 1502 92 685 83 637 612 1119 753 1127 273 1054 256 918 1590 1853 710 1377 413 458 1015 1479 622 1516 1491 1636 642 1888 260 1425 875 912 221 787 622 1245 733 1258 335 914 974 1399 757 1218 999 1009 326 927 328 1188 222 1298 292 844 354 733 1018 1480 510 960 319 1040 1176 1247 329 682 92 1260 644 1401…
Output: 9

Example 3:

Input: 2365 5676 1 2365 936 1237 224 456 883 2262 1335 1752 137 1729 599 2013 1682 1708 2099 2289 912 1428 197 1981 822 2076 1333 2329 720 873 455 2009 381 1945 1677 1679 515 1789 811 1858 1167 2260 102 189 1199 2007 228 1509 603 2178 339 2136 1087 1153 726 1817 1129 1796 1014 1552 364 1252 1714 2256 490 1395 310 1082 830 1611 712 2118 67 1727 1641 2171 1893 2051 859 1148 493 1917 661 1718 1233 2138 1383 2124 816 1883 101 2316 15 286 1493 2249 457 1349 534 1905 1361 1584 80 615 2275 2343 554 877 582 667 16 483 754 1348 1555 1583 70 285 262 956 638 1516 212 2036 531 1326 1378 1402 1815 2322 843 2133 968 1621 867 1200 350 1059 445 658 734 1346 544 2181 793 2092 179 943 1472 1878 434 585 264 1996 870 1353 1532 2194 190 229 880 1896 343 646 1502 1622 458 1798 622 2138 583 1696 148 1961 149 311 1255 2…
Output: 6

Constraints:

1 <= n <= 3521; 0 <= m <= 7042.

Loading...
Test Cases:No test cases
No test cases available.
Freya and the Fewest Hops - MEDIUM Coding Problem | CodeTikki