CT36786

Last bridges of Tailor

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Tailor runs the foundry at the poppy fields of Scarlet Plain. Today the books show a list of bridges, and the numbers must be worked out before sundown. 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 <= 1761; 0 <= m <= 3522.

Example 1:

Input: 1669 3405 1 1669 292 1310 1521 1557 218 1023 212 480 442 650 447 772 417 628 913 1193 1 560 90 1113 999 1400 878 1608 138 1506 424 901 878 1343 528 1388 551 1075 86 89 570 701 832 1490 387 534 1193 1496 302 1541 78 525 880 1150 122 853 2 311 278 1654 439 1077 861 1410 712 1547 849 1647 154 721 457 1235 1583 1668 357 824 345 1589 992 1477 544 1580 653 1601 407 1045 1221 1463 587 1529 987 1455 520 1196 682 1168 387 418 175 690 199 808 926 1512 443 940 335 510 82 216 593 1277 262 1378 906 1577 419 1432 612 1294 412 1004 291 1421 260 406 1299 1357 1207 1454 1035 1488 416 1251 1163 1254 38 1356 471 510 713 1552 537 708 347 1136 844 1611 321 504 1049 1241 725 1632 1207 1521 12 1634 698 940 939 1336 779 1299 563 1351 152 193 46 1625 618 1446 710 1427 1021 1629 63 765 922 1549 94 1192 562 1553 129…
Output: 6

Example 2:

Input: 1225 1224 1 1225 401 509 81 313 502 663 419 782 507 906 711 1122 929 987 133 279 121 1193 20 1024 43 694 519 845 498 500 405 523 671 714 1036 1177 329 776 1036 1093 679 743 152 405 742 992 65 132 437 741 231 1131 175 244 664 1074 792 800 383 450 708 787 593 1182 1091 1129 183 995 124 683 186 963 358 991 39 531 107 296 218 1192 849 1055 55 250 817 1087 63 379 43 786 269 947 508 793 316 323 526 1150 823 960 740 822 893 1066 226 426 197 752 220 1141 352 676 70 1174 483 491 155 161 695 996 226 280 324 1138 199 880 1054 1148 253 741 85 567 174 325 21 62 246 773 64 816 185 820 178 196 139 895 471 965 328 828 19 744 1127 1162 119 1001 44 168 169 713 244 516 314 1117 228 634 331 794 307 367 336 932 412 1145 532 883 140 522 256 871 361 533 27 492 213 811 875 963 474 566 422 423 101 663 316 772 154 …
Output: 10

Example 3:

Input: 358 3450 1 358 30 60 177 284 101 298 74 327 62 95 40 338 121 329 86 336 45 200 19 338 113 227 275 342 354 356 78 153 61 161 83 238 196 260 13 125 106 230 126 172 124 217 111 200 15 174 33 117 140 153 146 231 117 282 11 226 254 260 137 293 16 357 12 75 48 311 1 330 143 351 31 231 9 339 59 229 243 265 122 309 131 148 145 283 94 344 140 275 210 218 13 32 8 146 11 105 97 107 59 88 304 352 247 354 128 141 102 103 119 341 32 131 79 164 46 292 225 315 80 85 239 312 47 268 110 126 137 312 104 148 103 345 126 320 33 166 3 62 155 311 166 232 81 101 85 313 16 335 38 323 36 136 240 301 139 142 10 330 123 157 38 201 293 306 128 218 73 174 7 67 229 274 97 221 176 271 73 108 236 258 25 125 16 107 193 236 124 189 190 295 8 38 22 87 122 280 73 215 18 298 184 336 65 152 62 88 16 92 80 300 106 352 112 246 13…
Output: 2

Constraints:

1 <= n <= 1761; 0 <= m <= 3522.

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