CT33461

The Fewest Hops Beneath Serpentis

MediumL4 · Loop LordAcceptance: 0.0%XP: 35

It is audit day at the jade shrine of Serpentis. Zoravar spreads the routes records across the table and picks up a sharp pencil. 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 <= 990; 0 <= m <= 1980.

Example 1:

Input: 206 908 1 206 42 184 171 197 14 143 52 89 54 178 15 83 147 181 87 199 99 144 20 79 143 197 6 103 123 138 154 188 99 147 12 60 18 71 100 148 148 158 8 92 99 174 56 78 30 191 130 134 39 158 100 158 115 164 18 203 43 201 60 102 135 145 89 123 66 104 60 84 119 139 39 145 128 147 6 78 83 145 125 175 119 203 7 36 113 167 89 117 21 22 146 193 3 131 128 202 25 94 166 194 105 160 110 170 6 15 168 169 59 90 114 149 132 135 82 89 43 54 130 138 4 37 155 185 64 138 121 141 9 25 59 76 61 118 117 151 39 46 89 134 2 100 115 130 78 112 140 177 4 49 50 112 48 71 14 111 6 147 37 117 140 161 50 79 147 159 36 55 142 152 1 199 142 194 50 164 138 188 12 172 52 180 88 93 89 165 55 188 6 108 53 171 96 172 92 98 161 193 30 141 66 133 42 176 33 136 76 195 71 95 74 125 115 139 57 198 112 198 134 161 110 202 134 192 1…
Output: 3

Example 2:

Input: 700 1614 1 700 104 681 12 233 69 275 260 574 57 423 184 532 417 448 291 473 114 373 463 614 14 185 89 112 522 553 10 163 127 302 137 626 131 521 185 382 590 672 250 535 314 320 633 641 240 454 179 616 366 664 331 400 385 575 85 579 430 633 304 671 393 636 30 59 22 504 20 458 154 377 552 681 492 646 42 120 306 614 604 669 543 585 537 605 210 313 16 50 543 566 48 507 35 438 640 674 41 479 604 653 1 276 90 611 64 446 336 440 202 285 442 527 21 28 221 688 162 184 161 221 280 454 43 295 189 331 224 494 12 582 492 507 600 646 429 515 440 480 73 549 239 519 146 557 115 670 85 438 277 593 277 553 548 689 95 288 226 636 157 436 330 501 135 280 451 471 442 522 200 269 393 493 122 641 134 552 153 299 216 362 87 409 103 356 95 548 197 681 233 343 118 669 30 493 299 553 245 605 220 387 287 418 444 493 …
Output: 5

Example 3:

Input: 830 829 1 830 170 495 125 785 706 772 245 367 362 632 549 733 332 470 142 657 77 659 184 555 54 489 118 787 434 711 467 661 557 570 358 442 160 392 504 585 103 381 402 471 23 197 2 722 716 719 378 646 558 757 103 526 413 595 14 668 342 587 372 741 391 619 8 19 157 799 431 538 206 737 192 536 72 442 373 606 735 770 557 813 342 720 290 600 59 257 1 268 393 789 389 774 175 701 267 829 590 671 17 285 726 783 99 569 343 829 57 237 171 365 478 562 296 532 682 782 660 766 371 789 84 805 274 702 648 743 77 802 524 781 193 734 232 681 100 685 676 808 141 262 13 731 88 188 330 401 627 794 34 553 383 642 299 623 83 564 202 376 151 369 145 603 621 671 41 330 110 827 733 800 453 726 251 630 183 354 128 296 107 740 251 431 180 573 30 627 237 720 269 506 26 491 363 544 96 241 114 256 20 399 177 588 164 2…
Output: 9

Constraints:

1 <= n <= 990; 0 <= m <= 1980.

Loading...
Test Cases:No test cases
No test cases available.
The Fewest Hops Beneath Serpentis - MEDIUM Coding Problem | CodeTikki