CT37530

The Fewest Hops Beneath Winterholt

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Caravans arrive at the snowberry thicket of Winterholt with crates of routes, and Ishaan the bookkeeper must account for every last one. 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 <= 1058; 0 <= m <= 2116.

Example 1:

Input: 589 2103 1 589 70 183 275 348 73 207 141 299 140 165 33 35 164 253 7 522 2 130 21 393 222 541 254 275 65 236 372 425 305 483 255 588 406 548 247 276 267 547 248 462 1 522 87 245 83 484 141 290 332 493 72 459 504 536 170 439 155 536 312 486 537 582 145 252 281 582 281 566 132 318 90 538 460 543 507 587 60 178 13 239 229 434 135 577 302 312 268 333 309 521 32 432 413 498 160 581 9 155 7 340 317 487 39 277 105 530 348 392 137 196 204 500 331 426 346 576 432 588 245 429 235 571 194 382 406 432 296 501 311 349 227 421 40 68 1 584 66 490 360 383 104 581 275 342 80 580 269 343 69 179 194 431 256 276 551 561 448 560 45 73 137 304 356 554 271 551 207 383 211 390 479 578 313 582 57 129 296 438 75 129 323 397 118 240 325 404 220 354 142 419 63 544 45 428 382 542 147 503 41 241 354 458 14 266 21 427 3…
Output: 4

Example 2:

Input: 431 1217 1 431 176 407 276 277 20 218 90 413 25 149 214 408 146 360 34 239 56 377 229 320 250 337 94 325 363 411 115 311 311 359 313 327 126 377 25 369 61 99 126 281 260 342 4 92 184 389 81 210 315 399 30 158 145 366 354 419 23 95 139 285 217 223 75 246 214 334 36 179 148 167 65 258 183 341 75 143 45 95 381 404 131 205 94 287 88 117 198 207 59 409 20 253 350 420 81 205 19 238 139 335 57 69 121 220 258 311 80 358 196 328 228 400 159 422 29 334 107 308 52 121 188 306 188 316 44 147 46 308 248 296 194 366 69 392 94 129 172 195 127 359 174 257 3 67 298 415 109 188 75 209 57 420 246 252 97 403 87 157 83 103 156 350 17 310 417 429 270 309 75 309 322 395 326 410 38 375 213 391 126 233 168 229 64 312 177 381 100 423 295 308 34 58 181 315 270 297 27 139 307 350 29 269 318 396 256 271 323 400 225 36…
Output: 4

Example 3:

Input: 1006 1005 1 1006 260 332 326 575 819 934 679 947 487 907 303 950 748 877 674 817 680 948 184 885 196 787 665 929 796 884 386 924 588 668 260 916 953 1006 51 380 96 820 473 863 555 804 446 876 235 993 76 552 343 644 554 1001 225 980 676 723 415 967 134 839 116 486 493 764 281 387 509 949 558 636 91 574 91 364 273 412 270 881 66 638 483 510 459 969 330 335 97 418 269 644 349 390 99 633 573 933 29 246 100 363 943 951 260 581 145 942 72 266 93 936 646 796 354 883 458 518 326 661 223 703 82 121 323 465 606 922 60 345 372 1001 680 985 480 651 600 901 301 526 230 767 257 260 499 668 386 832 75 285 618 901 92 961 438 651 94 652 430 890 511 872 115 384 525 743 20 344 527 949 154 434 52 842 231 641 547 640 325 389 90 428 689 870 166 718 411 919 102 730 518 895 442 575 564 609 540 574 308 889 108 122…
Output: 14

Constraints:

1 <= n <= 1058; 0 <= m <= 2116.

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