CT30360

The roads at Petalbrook

MediumL4 · Loop LordAcceptance: 0.0%XP: 35

At the garden city of Petalbrook, Vani records each roads 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 <= 820; 0 <= m <= 1640.

Example 1:

Input: 21 210 1 21 11 14 7 19 7 15 4 14 10 17 10 11 3 13 14 20 4 7 1 15 14 19 2 8 5 12 2 5 8 15 15 18 2 3 11 20 5 16 4 6 4 11 2 18 9 15 12 16 2 12 2 7 11 19 5 18 7 16 17 18 4 15 5 17 6 19 5 6 1 19 2 15 14 17 1 8 1 13 15 19 5 21 13 21 1 12 11 13 14 21 3 5 7 9 10 15 17 19 16 19 9 17 1 10 18 21 16 21 1 16 2 10 8 18 9 19 9 14 13 14 10 12 4 12 13 20 9 20 13 19 2 19 17 21 12 14 14 15 10 20 5 7 11 15 7 18 2 13 2 4 5 15 3 11 15 17 1 17 4 5 4 9 18 19 2 14 8 19 9 21 6 7 4 8 3 8 16 20 2 16 20 21 3 4 11 16 17 20 15 21 12 18 10 14 8 13 6 17 6 12 6 20 19 21 1 9 19 20 5 14 1 5 6 15 6 11 12 13 5 13 12 17 13 17 6 14 12 20 1 20 3 10 3 12 7 21 4 18 10 21 6 10 7 8 7 17 12 21 5 10 3 6 1 14 7 11 1 7 12 19 5 9 10 19 3 7 11 17 3 19 9 18 5 20 1 21 2 6 8 20 7 13 18 20 2 20 3 20 4 16 3 16 3 9 3 18 10 18 7 20 9 10 11 21 4 2…
Output: 1

Example 2:

Input: 735 734 1 735 183 683 217 571 298 383 157 569 34 654 405 577 204 443 589 678 206 323 29 462 354 410 331 466 220 571 376 714 182 470 52 215 368 575 73 86 378 551 61 373 245 717 384 429 659 673 494 602 303 617 92 671 159 718 67 262 651 664 405 584 428 732 336 491 167 511 405 663 230 374 182 688 545 582 371 401 566 645 242 284 441 671 238 272 332 457 251 427 424 699 102 715 368 430 521 628 64 489 312 320 1 223 362 593 108 397 176 423 142 228 556 671 41 314 286 630 269 304 180 655 89 618 419 602 306 564 102 325 352 410 133 214 250 454 320 497 205 537 344 489 236 377 363 578 165 553 350 675 239 388 153 482 170 312 281 531 467 601 393 566 213 550 3 652 560 701 525 566 157 473 63 112 2 54 591 711 25 379 277 338 105 674 42 580 257 526 68 366 258 552 619 647 132 314 567 726 535 707 431 652 126 419 …
Output: 9

Example 3:

Input: 15 105 1 15 5 6 3 10 4 13 3 11 3 15 3 8 7 8 1 3 7 15 2 11 2 7 12 14 11 12 1 7 7 13 2 8 4 10 5 7 10 11 8 9 1 10 6 14 10 13 5 9 7 12 2 3 8 12 9 11 6 11 1 2 2 14 4 11 5 8 3 6 5 12 2 13 7 14 6 12 5 14 1 15 9 10 8 15 13 14 8 13 9 12 6 7 4 15 3 13 11 13 4 12 9 14 1 14 2 5 7 10 3 5 5 10 1 4 9 13 10 12 2 4 11 15 14 15 5 11 1 11 4 14 8 10 12 13 3 14 10 14 8 14 1 9 6 15 3 4 9 15 13 15 6 8 4 9 1 5 7 11 1 12 12 15 1 6 2 10 1 8 6 10 2 9 4 8 10 15 2 6 1 13 5 15 5 13 2 15 4 6 2 12 3 7 3 9 3 12 6 9 7 9 4 5 6 13 4 7 11 14 8 11
Output: 1

Constraints:

1 <= n <= 820; 0 <= m <= 1640.

Loading...
Test Cases:No test cases
No test cases available.
The roads at Petalbrook - MEDIUM Coding Problem | CodeTikki