CT42611

Envoy's Fewest Hops Ledger

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Envoy found an old ledger of canals in the shed attic at the salmon ladder of Rushing Falls. 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 <= 3083; 0 <= m <= 6166.

Example 1:

Input: 586 6014 1 586 180 195 95 332 54 490 157 302 266 519 197 475 117 285 216 288 72 388 318 439 355 475 39 580 203 278 357 399 162 557 275 314 49 520 97 344 296 436 347 443 212 333 340 474 150 271 148 229 133 448 11 202 13 14 286 550 404 555 171 299 199 471 508 521 245 293 26 60 366 443 377 450 307 313 113 364 164 272 320 549 526 527 205 464 231 367 156 488 135 578 83 172 86 527 57 540 465 526 23 80 69 293 161 473 388 455 16 265 6 365 330 368 300 420 43 175 33 463 419 484 146 202 291 420 321 384 174 226 13 125 218 512 6 232 2 32 278 499 425 501 204 580 111 119 175 260 351 416 313 424 450 509 48 265 100 207 239 272 277 323 91 116 3 74 28 170 463 532 305 489 2 192 329 383 437 526 295 415 239 286 7 534 142 218 77 242 154 522 38 215 358 538 345 399 70 548 439 487 47 548 144 500 122 217 204 584 201…
Output: 3

Example 2:

Input: 473 4895 1 473 186 196 106 193 58 104 122 233 3 98 14 209 112 347 102 465 171 174 102 203 210 328 66 119 134 153 309 458 50 94 35 416 236 331 37 296 46 427 70 184 33 387 50 149 365 460 419 453 391 451 115 428 17 462 221 256 141 414 45 383 218 409 152 358 1 153 92 423 181 338 387 473 341 379 194 276 196 236 110 138 284 450 62 197 279 284 128 134 203 301 271 315 421 447 389 398 246 408 64 436 11 41 369 454 184 226 437 446 85 166 268 341 21 175 386 428 282 375 157 274 277 286 148 226 415 423 23 472 56 93 345 373 213 449 130 252 56 453 50 178 372 445 83 254 2 266 229 315 24 442 214 379 70 327 88 394 222 418 249 278 273 363 96 417 1 113 194 290 37 251 140 190 229 341 67 298 26 254 310 320 54 299 174 190 348 350 83 91 247 325 65 307 249 403 292 454 139 143 87 328 38 134 49 348 191 195 71 418 341…
Output: 3

Example 3:

Input: 2727 2921 1 2727 391 2450 1315 2270 780 1737 195 2149 313 1264 567 760 563 2126 191 1847 427 1098 1324 2637 1186 1764 1455 1714 545 2517 1113 2080 1047 1584 373 2304 1687 2663 139 1911 936 1525 1127 1544 955 2339 823 2002 804 1013 200 1937 2 1585 1549 2676 1599 2465 1803 1913 1028 1409 1301 1477 1435 2413 206 2428 828 1860 813 1441 735 2656 331 2125 384 2185 1365 1406 1144 2560 1789 2048 412 1532 1254 1544 365 386 1116 2460 626 1714 257 2479 865 1655 1032 2514 1165 1922 602 620 97 1025 640 2456 824 2177 725 1320 347 2418 1097 2241 736 2647 1950 2134 546 1577 2269 2373 938 2094 99 128 1832 1988 1969 2623 839 1053 1630 2441 1655 1993 854 1516 1935 2010 94 2653 691 1238 601 820 743 1427 345 1575 847 2263 366 2699 1938 2396 739 2300 122 327 1916 2548 495 2056 2 846 2057 2687 867 924 829 1902 2…
Output: 12

Constraints:

1 <= n <= 3083; 0 <= m <= 6166.

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