CT54046

Chavi's tunnels Fewest Hops

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Every season at the quays of Driftwood, someone must rebuild the damaged itinerary. This year the task falls to Chavi, armed only with the tunnels register. 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 <= 1825; 0 <= m <= 3650.

Example 1:

Input: 870 1497 1 870 73 419 197 227 132 278 406 618 558 794 437 503 3 806 137 335 133 615 550 580 342 692 510 574 132 470 73 759 767 828 419 476 215 814 324 843 127 831 419 487 299 431 199 434 646 761 593 843 22 439 662 765 209 837 245 278 127 268 22 447 431 530 307 828 114 835 333 698 362 498 4 639 256 643 118 606 23 572 129 740 532 535 110 476 587 865 576 606 543 747 63 120 365 788 467 548 42 347 321 653 241 380 29 709 186 245 71 859 151 361 693 761 294 502 289 830 18 147 40 285 86 629 24 834 596 773 39 182 435 637 5 791 365 414 14 611 42 331 564 784 102 716 593 781 307 361 5 816 81 744 434 679 603 712 109 641 486 617 574 659 35 507 519 694 98 553 208 244 281 569 73 471 52 83 298 342 135 293 182 393 136 147 508 754 707 741 405 811 466 475 247 293 130 801 381 849 450 768 433 504 307 848 389 565…
Output: 5

Example 2:

Input: 443 2988 1 443 126 279 214 218 236 242 40 103 46 364 79 378 382 426 353 410 78 364 149 300 124 326 29 155 12 303 106 276 5 190 95 310 188 190 71 121 212 284 179 323 276 395 109 268 338 432 261 407 144 288 87 189 85 262 10 320 194 403 185 347 196 404 4 354 31 32 207 232 297 349 134 356 265 364 3 152 294 432 132 229 197 294 144 359 32 102 120 137 277 323 63 362 239 311 8 126 127 143 13 71 136 441 195 196 222 257 34 136 258 291 330 350 151 346 181 237 149 282 71 271 103 266 78 202 99 226 21 147 92 410 26 58 79 179 67 410 131 368 98 361 5 341 66 352 211 240 63 120 206 255 143 359 113 129 145 226 24 302 33 295 170 171 271 395 148 188 179 410 111 381 261 322 316 435 145 197 88 124 121 146 292 408 91 424 128 363 17 434 2 172 305 313 54 404 312 428 228 264 86 355 239 340 298 301 193 299 123 235 26…
Output: 3

Example 3:

Input: 895 894 1 895 28 599 437 723 351 419 549 680 241 242 643 687 506 638 610 687 260 589 405 748 508 700 104 692 123 326 351 605 717 866 591 715 686 709 386 478 127 447 526 860 241 839 111 494 359 709 81 421 202 852 20 386 440 773 94 849 602 809 37 386 397 479 92 302 551 828 355 459 50 479 155 195 510 839 444 744 607 789 315 475 43 821 68 235 609 866 275 557 400 600 80 629 88 351 156 845 16 505 52 86 317 377 300 504 50 883 183 633 401 568 84 232 756 776 150 535 579 692 249 877 773 826 300 682 33 479 472 569 28 354 556 650 110 555 672 875 165 193 156 888 521 658 258 857 491 600 101 296 43 540 624 887 19 662 381 485 804 807 283 381 7 553 571 786 439 441 791 818 225 269 252 835 386 861 284 757 334 743 111 691 447 698 758 761 491 617 381 625 480 672 243 362 454 706 387 698 618 860 452 499 100 775 …
Output: 13

Constraints:

1 <= n <= 1825; 0 <= m <= 3650.

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