CT36342

Kabir's Fewest Hops Ledger

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Deep in the floating docks of Skyharbor, Kabir studies rows of canals 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 <= 2865; 0 <= m <= 5730.

Example 1:

Input: 56 1540 1 56 4 24 2 42 19 30 15 49 7 51 8 53 29 50 11 44 9 27 15 39 31 45 3 52 5 14 24 35 1 50 10 47 2 17 47 53 29 56 16 32 21 55 2 50 27 29 4 22 34 40 11 25 11 49 25 53 19 29 1 54 22 49 19 35 30 33 11 46 12 34 38 48 22 36 6 51 18 35 49 52 12 43 15 25 13 27 16 46 42 43 20 48 14 31 4 38 18 44 19 27 18 45 36 48 4 27 38 44 4 42 5 28 10 14 26 36 12 28 28 30 8 52 1 18 22 51 6 35 26 56 13 52 15 56 8 20 7 33 33 48 31 32 36 51 32 49 4 11 14 46 35 38 5 40 19 53 33 47 41 47 25 31 3 49 21 23 11 47 29 46 1 55 21 27 30 39 35 42 13 24 5 20 43 55 12 33 17 42 28 40 54 56 40 50 5 56 37 44 3 39 5 42 35 46 12 48 3 9 23 48 37 46 16 44 15 52 16 24 14 50 49 56 7 42 19 34 23 31 26 42 3 4 34 46 23 47 38 42 40 55 9 51 31 55 14 16 6 33 13 56 45 46 2 39 25 43 25 46 24 36 17 36 27 39 5 26 21 51 5 49 12 36 22 39 37 48…
Output: 1

Example 2:

Input: 1457 1891 1 1457 45 1049 792 829 116 1209 502 933 583 1356 321 871 197 307 562 1118 464 721 1160 1200 404 1417 1242 1456 888 947 763 1451 770 935 588 906 182 1287 177 880 1052 1376 106 1030 98 625 16 963 1003 1053 452 801 119 1060 1045 1145 781 937 390 1386 581 1301 878 969 264 501 10 1071 303 1106 286 1261 9 901 520 900 259 914 1094 1404 394 988 271 1109 571 671 911 1278 206 357 1030 1086 355 780 673 1140 625 1155 12 955 123 520 465 1182 410 1321 425 1152 516 774 915 1290 129 206 49 783 63 193 524 620 590 862 555 1187 1136 1188 88 1117 527 606 17 820 707 1337 865 1249 55 1451 453 1443 21 74 405 420 68 1205 897 1353 245 506 454 1397 315 691 497 1421 312 1196 334 1038 606 1267 360 652 78 444 643 1360 43 1107 78 266 701 1129 472 1260 371 1020 281 346 405 659 281 986 97 469 783 1211 997 1345 …
Output: 8

Example 3:

Input: 1740 1946 1 1740 976 1092 173 601 698 1042 465 723 587 1676 148 1303 965 1302 894 1265 590 693 1198 1309 352 1612 671 1546 634 1185 86 135 519 899 345 600 604 1628 215 1384 214 222 1167 1740 1093 1295 667 669 459 1721 240 720 1099 1345 85 659 371 1156 748 1580 925 983 429 621 347 1647 436 1621 17 1432 255 1212 1116 1631 195 1640 1076 1405 959 1482 376 1163 1193 1264 1111 1415 337 1691 269 960 247 1254 1107 1628 675 1468 199 1110 531 1057 717 1131 1453 1705 1132 1305 19 705 337 1434 77 872 1167 1470 36 327 414 981 1326 1607 1283 1551 221 1316 1549 1652 933 936 217 1459 952 1688 316 1127 285 985 197 1694 913 1399 428 917 694 985 200 334 914 1738 465 563 1242 1297 499 959 1383 1705 291 1351 513 841 784 1562 693 1062 499 1181 273 1183 56 1431 495 500 809 1064 1065 1438 1355 1531 150 592 692 13…
Output: 11

Constraints:

1 <= n <= 2865; 0 <= m <= 5730.

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