CT34442

Wayward bridges Fewest Hops

MediumL4 · Loop LordAcceptance: 0.0%XP: 35

Deep in the frontier camp of Duskwood, Amara studies rows of bridges entries. One clean number will settle the guild's oldest argument. 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 <= 1620; 0 <= m <= 3240.

Example 1:

Input: 139 792 1 139 121 134 92 114 44 77 4 42 61 132 1 33 15 18 9 111 46 55 25 103 57 104 67 68 14 44 106 119 95 111 53 99 48 109 22 48 116 118 117 135 101 138 53 63 40 80 89 93 11 124 118 130 17 19 69 96 70 107 54 75 86 92 15 53 29 120 67 113 29 104 19 78 29 44 42 70 81 119 52 114 35 41 42 120 94 116 35 74 54 72 63 114 127 130 16 43 102 138 42 60 105 108 98 139 5 103 40 95 26 57 78 131 37 108 36 117 80 134 107 136 29 113 10 93 104 130 21 44 72 116 63 81 15 132 23 137 63 78 13 102 108 113 52 121 79 127 2 117 38 59 63 126 4 39 111 139 6 25 19 76 45 131 70 80 65 90 31 64 15 99 41 115 84 85 5 135 88 99 57 60 9 115 3 97 22 131 24 99 44 90 31 123 27 34 106 132 1 93 18 27 1 101 81 99 2 11 80 115 56 71 73 128 108 135 41 134 7 23 42 53 70 125 8 63 114 122 46 78 86 113 64 105 44 118 84 130 12 39 15 30 66…
Output: 3

Example 2:

Input: 119 673 1 119 53 112 22 42 11 31 4 100 55 104 29 41 19 29 56 83 54 104 11 72 94 111 41 64 17 59 20 21 35 73 11 28 10 83 76 104 34 119 11 35 48 77 60 65 4 33 12 103 15 24 39 75 75 79 41 68 88 89 17 20 84 93 17 91 22 65 22 27 42 82 47 73 70 107 39 104 69 105 58 109 88 90 11 26 36 104 21 34 27 80 6 44 49 71 7 67 55 87 25 55 40 42 36 117 99 110 48 96 97 108 8 76 24 104 117 119 8 99 92 98 81 119 32 81 26 44 5 86 7 18 82 91 78 107 27 118 23 71 2 113 36 82 8 105 85 98 70 108 74 78 3 37 28 43 37 38 14 69 18 113 16 19 88 102 45 93 75 93 92 97 16 94 17 114 7 114 82 94 29 118 18 51 20 39 15 116 62 116 5 7 46 107 73 80 9 70 69 92 29 85 69 98 63 112 17 102 66 86 21 29 5 100 29 53 56 65 30 49 55 111 34 53 64 104 71 114 59 104 61 70 57 113 29 73 42 115 83 105 75 111 44 74 59 84 49 50 60 104 85 89 4 106 3…
Output: 3

Example 3:

Input: 684 683 1 684 62 625 435 550 460 472 176 420 45 241 102 540 104 354 150 234 594 683 366 647 28 108 351 586 11 683 181 545 132 574 420 525 281 384 367 556 117 343 408 414 272 501 511 531 103 497 70 466 171 284 225 247 94 448 33 493 188 353 287 437 323 583 463 612 494 556 56 92 340 509 228 634 59 411 237 377 310 660 237 667 59 322 20 371 424 545 198 588 351 587 193 432 313 467 147 160 451 616 252 421 88 161 346 371 405 557 576 628 392 535 243 545 121 494 66 144 33 179 529 669 106 454 399 542 17 135 212 217 109 510 31 631 64 250 180 573 195 670 591 638 486 621 71 453 316 423 81 241 114 638 243 629 353 631 69 397 229 470 257 564 378 512 275 474 16 673 468 514 579 612 34 676 124 244 30 623 76 544 304 529 247 568 17 677 601 646 219 502 97 512 262 481 455 535 423 502 18 302 226 317 47 531 21 350 …
Output: 11

Constraints:

1 <= n <= 1620; 0 <= m <= 3240.

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