CT31779

The Fewest Hops of Rainhaven

MediumL4 · Loop LordAcceptance: 0.0%XP: 35

Iris the quartermaster watches over the monsoon port of Rainhaven's stores of canals. A careful computation stands between order and chaos. 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 <= 1390; 0 <= m <= 2780.

Example 1:

Input: 201 360 1 201 7 194 126 149 127 175 22 60 109 148 91 158 167 173 144 170 42 112 42 176 116 188 43 133 21 30 132 133 146 155 56 93 71 171 128 142 164 185 115 130 122 130 105 201 52 191 100 103 42 45 44 132 39 180 117 169 80 101 24 42 79 140 25 102 72 113 135 200 119 184 50 115 122 143 42 70 133 165 14 60 22 105 27 175 44 112 65 178 22 92 19 115 6 65 100 117 47 138 113 137 33 142 45 154 68 110 137 148 6 95 48 95 26 172 123 127 158 176 50 107 33 110 189 191 48 59 27 142 18 31 11 119 54 84 17 174 68 168 76 142 5 65 117 139 32 136 36 191 107 125 90 92 3 50 69 170 62 123 7 86 1 161 48 152 35 178 15 124 12 157 36 155 54 89 45 82 165 193 183 194 153 177 4 17 110 123 54 156 142 151 126 155 123 137 92 192 114 140 15 120 22 53 172 180 21 155 14 61 21 133 111 134 14 30 4 31 132 188 160 161 160 170 22 …
Output: 7

Example 2:

Input: 48 1128 1 48 21 30 16 37 3 20 4 48 1 38 18 47 9 11 21 36 9 39 10 22 5 14 42 47 15 29 6 32 2 33 7 45 10 36 29 37 8 21 1 4 18 44 1 9 5 43 26 28 10 25 33 35 4 36 11 17 21 35 20 37 34 40 18 24 36 47 17 27 19 40 14 16 14 21 8 34 4 27 7 35 34 41 11 12 26 42 28 31 21 22 5 28 34 35 29 42 28 39 27 37 28 36 22 31 13 47 16 48 28 43 14 26 2 12 6 17 6 31 7 34 16 40 2 48 30 44 31 45 16 47 31 48 6 28 18 35 24 36 19 38 29 32 8 33 14 27 28 48 25 43 41 48 7 17 4 29 26 43 15 42 3 16 29 30 32 33 30 38 6 26 33 48 6 38 2 9 9 23 2 3 20 29 6 19 19 21 4 39 2 8 30 41 24 46 19 34 3 47 27 39 3 39 12 18 5 40 15 48 8 27 39 42 25 41 16 44 45 47 13 26 11 40 14 19 3 30 23 29 18 41 14 25 7 37 17 19 3 45 26 30 24 47 13 28 16 25 1 5 13 32 27 34 7 19 7 14 22 47 33 47 28 32 16 20 4 34 1 7 6 46 24 40 5 16 13 45 5 20 4 10 4 19 2…
Output: 1

Example 3:

Input: 829 828 1 829 347 621 552 682 74 145 181 786 25 786 264 310 254 809 192 290 256 820 398 630 25 489 664 778 468 518 32 288 12 682 125 323 213 455 129 722 340 484 76 276 502 775 167 643 653 766 176 623 655 772 175 659 345 778 575 653 271 309 150 424 71 347 473 747 98 668 66 791 731 811 17 527 339 622 127 652 267 582 187 555 109 745 607 765 432 560 91 341 23 321 474 783 445 641 176 354 73 466 26 451 96 413 276 381 157 748 9 816 567 786 270 485 144 235 289 699 80 424 343 427 260 285 367 714 71 784 286 293 350 821 260 424 145 619 300 587 249 303 42 462 84 185 14 261 7 147 55 495 436 760 136 594 179 646 438 492 47 561 70 567 109 805 129 594 9 119 76 207 9 331 142 222 34 324 731 794 614 801 299 368 113 701 292 682 198 498 241 524 56 441 478 681 77 310 161 780 457 740 113 313 172 790 659 827 123 2…
Output: 15

Constraints:

1 <= n <= 1390; 0 <= m <= 2780.

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