CT32919

Finn's bridges Fewest Hops

MediumL4 · Loop LordAcceptance: 0.0%XP: 35

Caravans arrive at the fox den of Rustwood with crates of bridges, and Finn the scribe must account for every last one. 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 <= 1828; 0 <= m <= 3656.

Example 1:

Input: 836 3198 1 836 580 724 55 516 715 776 206 807 143 655 140 726 374 443 42 158 517 753 92 828 350 662 213 534 71 297 100 108 511 700 319 431 195 287 201 711 284 717 95 767 266 639 314 405 244 515 420 810 200 800 264 360 557 613 563 596 386 676 367 723 465 506 22 27 327 522 484 770 194 604 103 535 197 554 152 653 72 277 357 574 154 656 288 450 112 210 229 734 503 681 6 292 289 702 327 407 252 457 138 586 701 703 210 269 99 255 506 549 198 533 583 828 557 801 392 432 86 623 501 784 380 712 248 523 236 382 671 751 179 394 514 657 646 692 369 489 102 314 71 425 345 642 261 274 668 801 327 733 518 753 506 564 203 570 258 790 35 472 391 607 54 670 42 625 307 310 86 412 40 524 300 788 289 748 539 642 491 540 756 765 119 379 94 646 477 743 454 560 539 775 563 781 250 433 28 807 226 260 244 403 210 7…
Output: 5

Example 2:

Input: 1356 3208 1 1356 576 1199 1239 1344 86 796 858 1164 14 935 351 876 211 662 265 697 918 1005 52 1031 253 514 231 870 90 850 174 786 506 609 336 662 430 1186 409 987 116 1274 299 904 919 936 961 1036 626 1248 329 340 325 1032 310 1068 45 803 1250 1335 111 511 97 825 416 468 29 919 416 1095 291 511 121 843 270 488 109 314 214 896 90 1025 102 820 5 1078 831 1219 163 470 784 1245 331 1244 219 470 180 651 641 970 767 769 157 714 166 1264 503 819 1311 1349 1083 1254 643 963 47 522 122 139 636 1213 19 1299 193 1346 192 985 901 947 545 708 147 1261 577 582 938 1325 436 1023 527 1011 1126 1333 722 819 813 874 914 1083 352 842 880 1086 378 897 224 1169 87 1341 163 575 689 924 454 532 24 707 36 1053 29 97 183 881 3 611 74 1310 454 821 89 792 954 1298 766 774 887 1246 721 757 99 1237 212 1107 888 1099 …
Output: 4

Example 3:

Input: 542 3476 1 542 63 507 278 389 362 484 225 504 67 353 168 502 73 147 2 212 219 332 14 411 358 526 464 466 19 114 185 218 121 335 172 468 2 226 139 318 254 493 116 215 113 381 10 423 293 509 99 140 421 541 353 469 231 388 76 177 211 513 80 450 121 218 16 356 72 137 339 469 9 179 347 415 280 298 71 437 404 450 515 537 227 325 165 343 48 209 90 505 4 277 167 280 146 201 169 392 125 225 138 192 4 411 10 34 107 356 126 523 239 397 116 234 146 156 322 384 96 455 99 528 329 424 21 322 158 321 410 486 211 234 209 404 305 311 134 499 287 369 21 157 142 171 178 350 77 411 92 341 451 534 39 264 65 253 46 173 413 520 115 410 47 353 101 310 61 384 387 427 499 513 322 455 218 453 102 312 56 61 24 404 265 427 172 389 146 529 90 123 166 391 162 495 246 292 107 273 111 116 265 485 259 378 86 253 117 370 46 …
Output: 3

Constraints:

1 <= n <= 1828; 0 <= m <= 3656.

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