CT33132

The Quiet tunnels of Zane

MediumL4 · Loop LordAcceptance: 0.0%XP: 35

Zane runs the dairy at the canyon post of Redrock. Today the books show a list of tunnels, and the numbers must be worked out before sundown. 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 <= 1213; 0 <= m <= 2426.

Example 1:

Input: 882 881 1 882 381 652 286 568 540 556 605 821 446 580 409 423 25 293 210 758 167 696 272 798 109 500 412 720 206 691 388 540 98 820 455 573 314 668 51 858 55 156 202 344 256 347 382 868 407 576 44 616 348 527 56 503 63 862 57 371 511 605 211 819 48 574 267 808 584 654 47 779 403 836 647 859 499 785 409 809 44 188 375 843 359 621 510 519 111 860 361 412 490 602 187 199 431 614 152 547 186 244 43 247 93 236 170 183 354 390 650 771 121 562 126 715 287 729 345 773 163 814 68 503 305 606 641 837 112 516 572 797 213 879 251 795 197 506 51 198 414 705 290 422 405 439 514 722 195 218 99 446 177 722 125 395 229 867 44 101 136 142 104 275 136 789 202 631 732 751 357 662 278 502 582 664 534 744 742 848 297 428 366 810 9 34 585 808 371 574 639 805 560 756 113 868 369 865 420 813 4 26 46 853 416 666 12…
Output: 12

Example 2:

Input: 1035 1867 1 1035 423 899 204 434 321 1008 113 634 652 938 502 668 387 408 594 753 41 764 671 973 281 746 365 898 131 937 313 717 49 345 170 244 468 1006 67 946 411 706 405 641 21 861 31 797 104 709 430 711 766 806 144 773 385 899 335 449 37 365 184 469 20 62 276 288 177 196 532 536 143 430 866 1024 409 481 717 988 32 882 307 972 867 916 406 1026 833 870 382 979 133 318 55 866 1000 1012 43 496 124 807 594 895 579 621 209 803 377 852 311 980 128 401 76 529 11 389 283 743 305 569 145 259 352 505 335 558 59 906 123 954 251 621 160 223 81 562 191 464 569 784 90 789 136 821 207 566 207 277 636 687 912 1002 11 450 677 703 42 519 58 259 140 992 891 985 52 713 644 769 439 916 47 276 182 374 582 716 424 826 179 466 336 978 83 879 77 654 283 500 115 468 229 1022 471 578 98 741 12 76 340 935 345 837 2…
Output: 6

Example 3:

Input: 452 1782 1 452 396 398 23 77 191 229 240 323 343 352 343 370 15 66 219 401 205 392 56 214 226 339 217 434 66 327 71 128 272 377 234 361 62 416 68 80 159 238 277 436 253 401 240 373 109 319 240 245 238 399 192 356 303 423 313 369 285 438 181 275 46 422 173 285 7 292 101 193 200 445 391 418 67 297 24 144 117 145 174 311 360 417 4 48 53 369 280 414 144 190 155 401 253 270 152 401 167 285 184 185 328 410 123 161 171 423 74 394 312 427 356 365 213 411 52 295 60 375 120 267 66 232 48 332 230 327 208 284 5 45 164 435 198 394 351 373 339 397 192 404 125 221 13 379 97 271 377 404 29 414 7 398 70 359 179 300 355 385 288 375 14 389 255 259 188 345 30 217 106 230 33 247 223 321 77 209 28 186 67 223 216 240 160 323 55 324 228 241 235 441 168 304 230 387 104 323 316 371 170 314 41 169 76 196 242 287 180…
Output: 3

Constraints:

1 <= n <= 1213; 0 <= m <= 2426.

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