CT46243

Cyrus's Pale roads

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Before the gates of the ferry landing of Crosswater close for winter, Cyrus must finish the roads ledger - one figure at a time. 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 <= 2575; 0 <= m <= 5150.

Example 1:

Input: 2277 2276 1 2277 559 2163 213 2236 833 1839 1348 1378 5 400 309 1177 540 1865 669 1524 49 444 32 1000 991 1922 1065 1871 174 1317 684 1972 1075 1969 543 756 695 1249 67 203 1728 2212 445 1598 362 935 1534 2088 74 1621 630 1755 1834 1876 1099 1495 444 1845 26 797 674 1700 979 2256 979 2034 788 930 77 709 293 599 60 1855 386 1425 1101 1860 110 273 43 1372 2214 2253 1092 2199 600 1454 338 1827 737 1323 1654 1698 1249 1858 79 1466 303 1730 1344 1502 1101 1798 1648 1722 438 1933 736 1681 1167 1222 442 679 1452 2245 1332 1795 838 2011 447 1447 146 1049 163 170 601 2048 210 1844 28 1484 612 1729 1832 2158 707 1901 726 898 164 1201 632 766 52 337 998 2079 1338 1745 42 407 1674 1859 1094 1648 471 1999 20 1083 1797 2227 769 1965 1486 2157 348 1976 2021 2197 286 1569 1436 1598 767 1213 722 926 873 15…
Output: 14

Example 2:

Input: 638 3613 1 638 9 430 8 499 309 520 173 466 334 383 336 421 57 521 198 563 105 279 83 150 162 183 50 477 262 409 100 150 363 406 49 364 198 607 116 526 32 254 43 566 29 307 154 619 66 562 330 415 58 234 133 456 386 628 251 408 106 359 405 555 451 636 352 448 115 454 142 151 31 514 96 290 227 284 610 621 293 377 300 564 9 456 55 514 232 275 42 545 106 515 261 469 5 311 492 560 346 623 44 587 356 554 213 315 44 94 50 232 131 367 311 377 606 637 14 176 249 614 49 65 153 478 252 534 48 50 372 539 55 223 58 487 121 460 126 341 384 631 134 150 11 601 538 599 128 278 79 314 217 351 350 628 330 335 392 573 242 399 255 275 145 602 131 629 219 250 509 519 70 633 25 76 451 539 122 613 99 217 460 537 354 550 91 322 85 215 145 494 121 609 184 529 133 502 7 115 344 541 260 492 277 544 105 224 19 124 78 1…
Output: 1

Example 3:

Input: 1440 1439 1 1440 714 794 806 1066 324 1298 971 1009 451 1408 330 1238 238 1164 610 898 440 456 1127 1154 516 1325 236 317 698 993 311 1109 862 1399 97 827 841 1380 553 653 1428 1436 72 571 411 1154 363 1091 116 385 457 1062 608 1231 620 1348 884 1113 265 681 356 981 310 723 114 184 223 999 95 659 204 788 966 1296 218 886 591 1419 460 1340 791 1360 388 1033 35 892 418 866 855 1172 664 1086 449 983 592 934 1250 1379 52 936 92 1294 671 676 1054 1349 527 1241 595 639 1112 1235 588 853 901 1365 756 994 733 753 704 1419 1151 1330 64 686 1159 1248 427 1099 789 973 600 1275 634 1433 78 144 473 955 428 1061 548 606 1020 1136 100 1205 855 1139 770 1237 1251 1415 489 979 11 337 504 1356 19 95 663 779 922 1048 330 469 426 1092 298 974 43 819 208 443 659 1254 935 1044 751 760 602 922 423 685 618 1345 6…
Output: 11

Constraints:

1 <= n <= 2575; 0 <= m <= 5150.

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