CT31747

The Sterling roads of Warden

MediumL4 · Loop LordAcceptance: 0.0%XP: 35

Every season at the cliffside roost of Stormrest, someone must inspect the delivered goods. This year the task falls to Warden, armed only with the roads 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 <= 1700; 0 <= m <= 3400.

Example 1:

Input: 720 2661 1 720 559 576 457 533 434 677 348 562 99 569 647 698 156 361 230 423 187 189 58 137 509 534 88 690 220 652 150 327 43 128 613 714 403 709 50 395 35 121 569 709 25 410 537 624 476 651 246 455 563 575 59 110 342 589 120 423 419 712 87 232 139 472 313 505 47 173 8 626 56 166 96 456 685 691 422 467 4 37 58 467 230 418 18 38 31 475 43 639 10 215 263 459 428 695 276 638 160 694 586 618 399 593 27 454 335 536 22 91 277 382 412 720 130 257 125 569 56 631 53 522 47 475 245 438 241 289 335 535 299 385 183 199 270 283 215 574 482 652 532 634 409 477 506 560 217 635 400 669 186 559 11 510 22 213 307 442 31 701 292 594 331 671 303 589 324 342 259 285 93 395 315 478 50 484 134 708 68 376 141 572 414 432 259 303 73 623 471 541 51 490 205 503 243 719 56 620 439 480 351 678 110 597 118 367 85 245 …
Output: 3

Example 2:

Input: 645 3388 1 645 299 394 480 532 18 385 53 152 238 317 314 393 444 468 383 397 166 591 468 552 171 576 231 545 10 485 324 535 173 508 185 340 189 602 289 317 120 560 28 572 294 531 39 456 215 534 330 509 69 186 20 567 291 315 605 623 276 572 397 608 351 507 230 496 206 451 334 466 31 282 366 441 456 552 299 573 394 586 223 548 43 426 200 231 176 380 203 271 144 626 150 518 245 442 511 634 351 368 163 328 411 635 147 533 343 514 196 631 233 561 23 396 209 216 79 392 8 292 131 397 83 297 41 303 487 637 119 545 5 341 232 363 28 191 281 588 74 621 233 424 233 640 83 590 30 308 26 624 205 642 268 381 231 450 11 613 212 278 214 641 336 345 14 353 305 345 121 122 281 370 38 633 328 460 280 501 164 249 251 453 107 414 89 408 309 584 282 382 83 377 553 608 25 167 351 606 371 479 464 607 187 249 343 4…
Output: 3

Example 3:

Input: 69 983 1 69 33 34 25 35 36 39 46 65 22 48 45 52 20 56 5 36 43 46 46 50 9 22 36 57 19 37 13 28 47 65 1 2 33 55 12 25 8 60 20 42 16 61 1 15 23 54 20 53 5 6 4 18 18 54 17 56 6 11 51 61 22 30 5 22 2 45 20 68 2 51 6 44 15 46 22 44 12 35 33 54 2 14 28 44 7 12 1 61 66 67 45 68 21 34 5 49 12 42 15 52 17 28 2 16 21 33 52 64 12 43 12 68 8 35 8 20 36 48 7 45 51 60 35 61 19 24 55 58 6 33 50 52 7 34 23 65 28 49 23 46 17 67 49 54 19 39 14 59 60 67 50 56 22 64 15 45 12 37 21 59 7 42 11 55 43 49 16 23 4 39 54 69 7 18 9 19 36 49 25 60 36 61 20 44 6 64 48 67 37 40 21 26 16 24 13 35 45 46 31 55 19 23 45 57 23 51 2 24 17 31 42 49 28 47 11 24 20 63 6 45 25 36 27 65 21 32 8 63 24 56 8 29 15 56 34 45 27 66 38 42 25 38 37 50 35 56 45 48 14 23 27 54 22 68 54 64 18 28 12 44 27 49 28 50 62 67 14 68 53 54 67 69 17 34…
Output: 2

Constraints:

1 <= n <= 1700; 0 <= m <= 3400.

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