CT32031

Seth Counts the tunnels

MediumL4 · Loop LordAcceptance: 0.0%XP: 35

Caravans arrive at the cinnabar mines of Vermilion with crates of tunnels, and Seth the clerk 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 <= 1229; 0 <= m <= 2458.

Example 1:

Input: 1107 2306 1 1107 121 569 533 866 603 636 153 291 648 933 833 1103 539 584 712 773 329 387 124 704 465 599 190 528 876 1078 408 1025 523 1000 163 660 571 699 234 873 424 608 352 369 299 376 157 1027 252 563 67 422 381 951 563 846 248 589 591 1025 621 932 821 828 105 384 665 913 363 743 827 885 203 1025 757 781 106 763 460 578 491 621 253 422 796 1082 177 620 686 1046 731 824 320 783 509 783 755 883 226 837 1029 1055 959 1031 418 833 275 1053 26 386 465 556 35 286 568 649 51 514 603 828 125 787 705 998 50 1025 40 402 25 369 198 731 173 233 553 835 50 682 649 977 157 442 426 791 407 988 159 758 248 309 264 1001 154 696 698 860 420 899 157 1068 482 740 376 783 148 352 775 924 57 1010 293 304 536 1031 680 845 118 574 989 1076 394 470 273 617 61 286 37 159 629 672 412 1106 46 935 498 685 602 756…
Output: 4

Example 2:

Input: 438 437 1 438 302 337 122 340 36 45 197 348 100 233 72 162 17 352 167 186 122 233 94 151 29 162 91 182 91 207 104 155 25 47 102 308 106 140 184 404 38 235 44 180 296 435 22 264 254 301 176 337 199 382 123 422 69 237 107 370 228 309 77 253 53 188 324 348 111 358 220 348 336 414 86 351 108 354 194 412 195 424 168 351 1 252 177 339 309 412 205 385 382 404 333 416 103 366 22 344 63 190 180 363 31 261 105 317 261 418 328 357 279 300 71 173 117 170 71 345 210 240 359 374 361 385 175 346 67 381 24 308 239 394 343 431 142 337 41 426 20 391 49 51 160 233 94 125 297 369 19 221 51 180 19 343 244 382 179 323 68 336 236 320 73 214 64 421 11 217 106 330 8 149 111 435 227 295 34 122 69 129 41 269 143 326 36 407 284 409 96 138 9 276 117 350 4 131 253 405 70 144 343 423 65 242 308 419 161 279 262 337 32 11…
Output: 12

Example 3:

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

Constraints:

1 <= n <= 1229; 0 <= m <= 2458.

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