CT36302

The Quiet Fewest Hops

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Chandler runs the ferry office at the snowberry thicket of Winterholt. 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 <= 1851; 0 <= m <= 3702.

Example 1:

Input: 468 2980 1 468 331 345 118 316 50 401 206 308 188 264 214 398 239 351 224 435 357 459 218 438 234 291 159 262 158 421 87 453 168 347 444 465 298 344 22 156 289 444 85 332 183 206 427 445 90 247 34 397 101 450 145 343 37 179 13 441 111 229 255 387 70 285 108 116 16 108 22 256 22 35 97 180 197 329 105 151 139 228 86 267 364 430 80 113 340 345 184 426 276 288 234 419 34 370 243 446 288 429 339 422 235 454 141 345 30 116 34 189 44 410 234 320 34 372 134 298 190 238 182 183 327 346 18 217 198 446 245 440 152 257 14 451 16 239 398 429 426 453 360 458 362 368 299 361 52 204 447 463 158 191 157 211 42 452 268 385 384 424 38 267 150 271 216 448 31 295 320 461 109 180 118 191 220 430 49 149 99 309 139 386 271 295 259 465 14 379 314 443 274 408 63 111 49 307 155 454 90 406 2 335 134 348 246 424 33 77…
Output: 2

Example 2:

Input: 925 3267 1 925 647 777 743 762 624 785 149 538 156 284 135 757 295 406 90 276 587 643 419 578 570 895 462 755 725 918 72 776 512 860 514 593 262 786 875 878 190 603 231 663 309 731 472 662 311 478 476 697 311 497 775 802 244 891 228 557 586 726 18 167 208 734 609 784 200 621 18 912 30 489 61 614 734 922 442 662 189 805 730 770 291 479 727 803 56 262 800 890 265 896 598 761 273 920 16 364 446 864 226 232 138 699 602 790 6 540 35 262 389 715 256 520 40 791 440 671 49 595 582 744 62 610 179 775 140 284 409 430 156 886 490 748 301 747 829 870 161 490 703 841 619 788 642 889 212 530 71 794 29 837 165 234 787 798 318 639 250 407 93 850 294 558 295 320 257 269 3 346 62 461 391 826 700 854 125 462 60 482 428 648 227 589 343 832 370 660 63 170 151 284 739 835 596 765 19 495 246 719 289 893 244 642 …
Output: 4

Example 3:

Input: 1574 2877 1 1574 367 1537 410 1088 323 1535 890 1395 146 477 121 1291 1170 1442 282 953 59 211 1465 1510 475 1221 204 463 579 821 654 675 989 1284 739 1565 226 871 75 500 197 1051 219 900 238 539 1162 1438 936 1467 354 770 615 937 696 714 250 1003 108 761 1372 1494 7 1277 574 1359 119 1534 79 186 672 1069 564 1287 416 1088 874 1116 99 1264 619 751 546 1512 64 411 137 1472 374 1062 120 876 429 970 1066 1346 717 959 457 1213 261 870 1060 1357 422 1136 1071 1227 446 729 706 976 51 358 506 1121 809 1335 1262 1545 1209 1546 601 1153 306 1000 479 527 1101 1139 1158 1340 248 949 67 1553 715 776 1017 1163 489 1518 993 1055 248 898 114 389 875 1295 353 985 217 811 546 878 105 294 560 1151 82 160 198 1526 15 1005 288 896 377 566 1047 1076 440 459 768 902 561 1503 326 1064 912 1027 133 209 650 1164 1…
Output: 6

Constraints:

1 <= n <= 1851; 0 <= m <= 3702.

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