CT31798

The Coralcove Fewest Hops

MediumL4 · Loop LordAcceptance: 0.0%XP: 35

Legend says the vault under the island market of Coralcove opens only for a perfect tally of routes. Aldo means to find out. 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 <= 879; 0 <= m <= 1758.

Example 1:

Input: 210 1552 1 210 166 193 33 155 12 202 4 48 21 98 123 129 31 134 11 115 19 177 38 80 17 198 158 194 114 115 147 197 203 205 82 187 18 112 67 157 56 93 13 156 53 145 38 200 55 193 194 208 69 91 110 155 38 68 42 95 34 85 104 182 76 136 76 132 86 130 2 199 128 199 84 97 146 177 40 204 78 191 151 168 36 162 113 159 195 209 7 93 178 210 17 53 20 205 8 51 14 85 103 169 55 94 171 194 4 22 172 185 131 189 98 129 102 164 80 139 77 88 45 145 146 171 12 77 39 66 15 126 141 155 91 168 108 139 9 75 37 83 8 153 81 134 88 154 103 125 11 160 147 155 148 173 37 125 1 52 136 208 4 86 30 68 7 208 102 201 175 180 27 145 108 174 55 177 130 144 12 106 46 172 43 57 21 189 32 108 154 205 31 139 51 128 126 169 66 78 26 183 85 97 177 198 39 157 135 141 4 91 65 183 27 158 134 151 57 200 67 70 8 168 119 157 11 153 80 1…
Output: 3

Example 2:

Input: 29 406 1 29 8 15 9 24 7 16 5 8 4 21 14 19 21 27 15 25 17 21 20 23 7 11 15 29 18 27 14 15 6 24 25 29 13 24 7 9 12 16 9 20 17 27 11 25 9 29 14 17 11 21 9 15 10 20 23 25 13 16 2 28 10 17 27 28 7 29 20 27 11 29 15 26 2 20 3 21 11 13 8 25 13 20 1 27 4 11 4 19 13 18 6 9 2 11 11 12 3 20 23 26 3 17 18 19 1 8 3 8 21 23 1 18 6 23 15 16 10 16 2 6 5 15 3 10 14 23 18 29 5 22 22 28 16 27 7 19 7 20 23 29 7 22 1 21 4 18 13 21 5 29 7 13 4 12 4 26 9 18 8 12 1 23 10 23 3 28 12 20 8 13 2 5 15 27 3 22 10 21 15 23 21 28 18 20 4 14 13 14 23 24 18 21 1 12 19 26 7 10 12 27 4 27 4 8 13 29 24 28 24 27 9 17 12 19 9 19 17 22 12 21 4 13 2 23 20 26 1 16 9 26 9 25 1 6 9 16 6 25 16 18 7 27 7 26 13 15 14 21 2 17 13 25 5 28 2 21 11 27 3 19 5 21 5 10 1 20 1 9 12 25 4 5 5 7 11 16 17 24 1 28 11 14 6 13 8 18 15 28 7 18 1 7 6 15…
Output: 1

Example 3:

Input: 680 1687 1 680 2 139 63 305 367 530 203 633 126 320 146 287 74 430 95 558 158 510 26 243 157 516 195 663 424 538 35 443 486 537 57 160 28 247 112 426 240 371 207 481 92 337 586 628 546 606 31 601 476 646 250 409 181 493 589 647 127 134 188 658 186 196 103 329 93 545 64 527 251 389 209 554 204 295 35 568 257 464 367 436 450 536 49 658 140 180 21 353 11 151 478 637 289 309 79 384 275 673 328 626 117 279 109 351 355 413 373 549 269 382 116 506 140 311 321 587 144 153 269 478 71 246 9 367 1 364 358 390 113 375 169 606 183 304 541 610 504 678 97 506 208 547 513 600 95 600 64 198 114 502 163 523 314 619 50 428 459 567 124 408 637 668 246 299 206 411 584 608 26 536 325 372 491 675 134 652 234 390 555 566 530 679 605 610 199 503 172 291 354 583 366 660 1 569 377 568 6 547 225 317 511 645 62 216 27…
Output: 4

Constraints:

1 <= n <= 879; 0 <= m <= 1758.

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