CT47612

Uma's Indigo bridges

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

At the seal rocks of Barking Cove, Uma records each bridges in a worn leather ledger. The guild wants answers, not guesses. 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 <= 2289; 0 <= m <= 4578.

Example 1:

Input: 1755 3010 1 1755 1275 1541 148 580 434 477 132 458 1300 1749 1496 1518 32 75 1340 1570 71 1123 328 1059 756 1495 302 831 223 644 774 788 534 787 321 960 676 1196 838 841 1420 1593 1532 1567 27 1193 893 1118 1269 1472 589 1367 614 1547 378 1598 184 776 697 1656 186 1591 1300 1751 338 1031 1383 1433 868 1599 584 643 892 1722 318 907 912 1491 1277 1519 483 574 992 1737 826 883 326 1241 499 571 1345 1534 224 895 619 1057 317 1278 40 524 389 917 713 763 877 1490 1015 1590 26 421 1402 1566 203 1320 1194 1716 698 1581 187 598 1432 1463 134 1254 647 747 509 1378 246 1659 41 551 784 1637 93 902 7 1247 147 310 679 1667 627 1702 1105 1358 338 443 856 1084 222 1088 419 815 681 708 635 1583 527 903 1032 1455 180 265 872 1299 1106 1442 825 946 429 762 398 694 1441 1647 623 1301 800 1439 144 1532 31 497 …
Output: 6

Example 2:

Input: 1761 4294 1 1761 1607 1702 546 707 1430 1650 208 1518 824 1180 54 784 1110 1183 620 977 209 241 124 564 342 839 767 1237 589 1627 34 1083 1215 1579 491 498 125 1297 191 906 756 1153 1267 1592 796 1010 370 1000 1010 1169 94 1035 683 1495 95 406 1435 1654 271 1301 851 982 21 1500 55 278 1077 1722 1227 1314 195 378 685 1076 1087 1211 161 1019 674 917 417 1345 476 581 391 890 267 787 1512 1560 372 1612 325 1277 134 1462 139 1003 923 1181 368 1258 333 854 81 1336 68 1449 1499 1715 508 1301 55 671 41 1533 915 1156 20 717 16 488 4 589 278 1675 1444 1459 1094 1129 241 646 624 762 282 741 87 276 220 789 1387 1660 12 1686 321 949 907 1351 458 825 629 1242 125 273 306 841 227 1720 393 727 533 549 85 860 1046 1657 4 520 1146 1659 376 1011 1385 1494 128 717 155 251 865 1656 274 1617 211 1718 348 866 74…
Output: 5

Example 3:

Input: 228 2262 1 228 164 227 41 48 85 150 77 167 5 148 178 214 148 155 15 208 78 104 80 223 71 195 114 211 143 162 159 188 20 183 115 220 215 225 154 217 35 146 10 29 183 204 53 64 139 222 43 96 191 196 150 184 95 140 3 194 64 160 200 217 52 62 174 190 100 206 89 183 27 222 9 193 153 182 109 201 81 161 14 28 23 142 26 207 94 134 13 115 83 136 171 173 41 211 77 153 23 204 4 218 21 38 114 203 101 148 65 165 54 164 98 133 60 193 128 175 25 44 107 197 49 97 49 129 146 210 22 74 66 155 61 136 54 221 120 130 10 202 147 211 14 149 111 195 83 219 121 192 29 184 32 199 37 133 77 94 105 165 155 195 91 181 39 72 43 86 174 212 135 216 66 96 177 208 7 182 66 101 52 199 173 198 4 27 139 174 21 123 194 220 5 136 10 201 14 101 154 216 92 149 44 96 86 170 137 173 36 100 119 123 56 83 17 41 34 174 27 148 48 52 11…
Output: 3

Constraints:

1 <= n <= 2289; 0 <= m <= 4578.

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