CT38469

Finn's Ancient Ledger

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Every season at the pine barrens of Needlepoint, someone must restore an old family record. This year the task falls to Finn, armed only with the routes register. 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 <= 1812; 0 <= m <= 3624.

Example 1:

Input: 1695 1694 1 1695 691 1285 370 405 242 942 302 1290 1548 1640 14 1122 1174 1262 33 1309 894 1052 803 1380 187 1383 320 1059 1101 1654 465 1098 840 1524 638 993 570 851 1127 1518 333 930 1060 1322 375 464 1440 1535 348 1396 1338 1641 397 1668 145 1480 128 864 270 1232 509 1607 211 990 679 1250 507 1534 447 696 53 456 258 1683 727 1509 390 503 102 601 700 1222 326 930 301 653 1096 1436 185 1417 704 1424 1118 1185 442 475 1399 1423 441 1371 167 766 552 580 214 1407 844 1086 1265 1370 203 787 297 1319 1170 1676 1471 1612 469 1640 441 477 666 1065 957 1059 535 1627 149 1389 1306 1616 376 1580 727 1572 335 800 1264 1328 918 1685 1193 1474 458 1119 18 142 666 1081 120 475 855 990 35 759 1166 1442 904 1224 155 886 1415 1687 178 1565 298 421 271 928 221 1155 87 321 780 1376 310 654 201 234 891 1102 …
Output: 18

Example 2:

Input: 1473 1884 1 1473 366 1415 256 409 507 1288 167 759 449 824 319 491 736 845 747 836 1169 1257 1301 1304 64 1266 66 155 351 543 104 1160 628 1400 240 1422 859 1062 14 1026 144 787 556 1321 186 798 1 813 438 514 599 837 240 1055 145 539 492 794 843 1142 667 728 206 1056 64 769 312 871 879 1146 1243 1399 129 979 111 336 547 560 1121 1176 545 613 569 689 236 917 477 1205 584 595 352 409 511 833 985 1449 696 877 73 1427 362 1430 85 638 1001 1043 286 1035 451 1419 356 1031 1005 1040 487 587 1181 1471 19 460 197 370 929 1198 928 1028 291 1382 239 591 765 1072 186 490 62 840 264 1402 688 1202 701 1219 54 930 1305 1366 92 1191 949 1268 336 337 745 749 75 932 197 1280 373 749 156 1064 786 1331 28 1129 169 887 624 678 276 1456 62 1137 501 575 745 750 1013 1473 463 1172 1024 1465 943 1304 893 1325 252 …
Output: 12

Example 3:

Input: 1184 1183 1 1184 295 690 729 880 165 765 78 628 532 1043 543 1157 50 189 84 576 389 554 111 505 605 758 617 720 523 998 365 1169 726 842 888 1070 63 650 227 868 785 975 395 505 233 1082 45 976 152 340 308 758 836 1071 336 592 365 503 891 1070 301 688 559 601 856 1168 757 835 108 436 716 759 179 532 701 952 234 754 707 1003 633 940 466 857 412 1178 533 669 557 983 171 376 18 1116 375 967 402 1048 720 763 908 1174 377 744 343 1055 178 271 880 894 107 1066 760 948 348 969 292 1028 882 887 416 550 156 391 364 744 882 1048 804 930 315 703 245 654 1001 1166 812 971 367 937 277 681 326 936 194 934 977 990 126 1109 491 640 249 656 634 904 176 693 971 1037 327 769 630 921 571 892 383 521 169 820 968 1134 56 1010 120 269 52 396 158 170 875 1159 111 492 646 1054 702 1086 914 944 235 667 593 635 420 1…
Output: 8

Constraints:

1 <= n <= 1812; 0 <= m <= 3624.

Loading...
Test Cases:No test cases
No test cases available.
Finn's Ancient Ledger - MEDIUM Coding Problem | CodeTikki