CT29436

Varun's Fewest Hops Ledger

MediumL4 · Loop LordAcceptance: 0.0%XP: 35

Varun found an old ledger of canals in the mill attic at the zephyr cliffs of Galeholm. The margin notes pose a precise question. 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 <= 1060; 0 <= m <= 2120.

Example 1:

Input: 394 1437 1 394 73 167 226 366 26 151 176 178 316 327 385 388 309 332 118 317 132 352 3 62 50 260 335 383 114 202 5 301 214 359 126 372 24 128 172 335 92 280 210 217 139 300 84 219 121 181 310 350 170 358 42 241 274 386 183 388 91 204 268 362 25 287 165 238 99 297 309 390 173 265 42 295 42 73 362 366 164 224 179 246 173 355 92 105 289 389 74 350 95 271 226 237 130 132 120 356 18 305 77 111 53 202 4 388 75 317 38 208 151 313 188 212 28 150 136 283 169 176 151 196 98 376 284 347 54 362 195 312 8 185 50 229 245 265 44 162 10 176 67 359 24 28 28 324 124 172 201 268 136 204 61 293 38 371 251 337 337 392 320 370 49 93 66 183 208 239 257 271 151 303 212 258 269 363 221 232 304 329 76 247 220 340 135 210 243 375 137 263 221 291 364 371 56 252 288 374 257 311 211 375 54 273 92 222 123 342 41 287 197…
Output: 2

Example 2:

Input: 655 1206 1 655 407 538 73 208 100 620 213 248 187 390 121 637 364 384 520 586 153 585 179 496 252 532 42 511 234 263 359 568 142 473 98 400 71 269 91 613 147 454 191 292 3 414 22 436 26 371 465 480 42 153 216 269 207 621 6 384 60 496 82 564 109 228 307 593 125 459 258 469 515 536 143 449 401 436 526 542 35 638 133 551 164 278 183 560 85 207 25 376 82 543 93 404 301 561 162 646 30 398 68 643 82 340 478 551 345 536 436 445 260 262 151 263 113 180 99 516 187 525 229 545 431 455 18 560 9 518 264 347 252 494 201 600 228 452 141 476 135 407 101 635 112 185 172 551 355 361 71 412 26 85 211 437 321 564 44 143 146 221 616 629 257 359 211 599 424 497 389 394 260 381 128 439 183 332 3 51 44 211 491 636 16 54 375 405 126 579 80 636 150 599 450 495 266 331 216 520 254 464 265 276 162 378 320 566 402 63…
Output: 6

Example 3:

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

Constraints:

1 <= n <= 1060; 0 <= m <= 2120.

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