CT55187

Finn and the Indigo bridges

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Every season at the mushroom groves of Fungaldeep, someone must verify the ledger before the auditors arrive. This year the task falls to Finn, armed only with the bridges register. 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 <= 1330; 0 <= m <= 2660.

Example 1:

Input: 99 1478 1 99 24 28 25 53 10 42 55 89 48 62 59 66 86 89 18 19 40 41 78 89 7 91 2 84 58 86 60 97 38 58 28 31 22 98 51 90 10 26 21 53 23 64 53 80 11 87 11 24 41 94 15 55 25 58 37 54 21 81 15 32 65 93 23 68 42 73 2 82 30 40 72 74 51 78 13 25 13 90 72 95 81 97 51 99 55 99 61 82 58 60 64 86 32 87 55 62 6 45 74 98 22 26 57 69 87 99 29 86 2 76 55 90 49 84 49 91 7 64 57 84 61 92 4 72 43 98 6 11 54 92 33 38 18 96 12 90 22 85 35 82 4 11 42 93 42 72 53 95 15 29 10 91 41 62 46 69 18 92 67 93 16 84 20 92 11 94 30 38 64 68 57 82 16 17 48 92 1 15 2 83 44 77 13 70 35 98 5 48 8 83 47 55 39 83 6 55 10 49 16 60 48 77 48 94 26 33 25 43 36 82 47 81 57 72 93 95 33 63 31 89 34 87 9 57 28 49 5 60 15 37 80 86 39 94 7 30 37 38 15 72 63 74 65 90 9 82 12 84 22 59 28 32 18 56 11 85 67 83 41 67 1 52 3 25 34 70 30 86 15 …
Output: 2

Example 2:

Input: 456 2541 1 456 254 342 154 186 21 69 77 258 51 247 283 292 436 439 93 407 137 210 150 437 132 272 153 383 152 310 60 354 87 314 151 324 125 339 173 449 355 407 180 359 225 298 147 334 104 150 59 355 58 314 120 199 2 456 5 398 204 419 162 243 104 424 177 269 108 148 314 361 44 175 81 331 296 401 37 268 282 415 3 82 266 292 255 356 380 416 37 143 45 171 194 349 241 447 156 365 157 423 210 327 47 315 246 334 3 237 349 353 45 248 165 187 28 415 48 305 361 455 151 449 190 321 55 254 44 294 72 344 228 309 47 183 80 85 274 391 30 171 169 375 365 421 105 193 233 262 270 435 40 177 8 75 147 332 90 431 243 317 75 244 60 379 137 389 429 440 173 181 95 139 19 376 26 413 146 306 313 433 66 369 42 128 81 217 178 399 214 328 227 270 1 75 57 250 375 448 305 451 277 412 95 353 91 265 125 171 19 272 45 90 1…
Output: 1

Example 3:

Input: 1104 2161 1 1104 615 835 355 626 505 896 40 385 311 456 693 958 374 908 404 408 253 903 686 1020 820 1022 731 836 222 384 61 160 240 747 54 914 24 887 107 290 35 96 12 740 415 750 63 88 354 796 311 852 165 211 461 796 189 1085 15 951 179 1039 267 681 388 605 292 689 571 746 350 1076 33 1004 33 420 84 1052 414 717 102 975 150 816 627 899 404 940 127 974 71 375 883 955 67 573 95 596 183 531 448 604 766 915 905 907 363 515 290 521 25 309 257 874 170 870 350 380 669 874 356 839 86 231 560 781 248 495 217 649 33 287 13 703 217 911 479 723 2 192 559 910 255 830 330 1015 573 584 533 1062 357 719 179 463 855 932 13 853 308 384 89 358 177 944 643 646 787 1047 422 868 565 742 102 223 998 1028 47 362 68 990 257 669 56 824 166 670 435 948 47 933 287 791 255 918 275 562 870 879 281 1064 73 1003 110 230…
Output: 6

Constraints:

1 <= n <= 1330; 0 <= m <= 2660.

Loading...
Test Cases:No test cases
No test cases available.
Finn and the Indigo bridges - MEDIUM Coding Problem | CodeTikki