CT52175

Ulrica and the Violet tunnels

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

The council of the alabaster quarry of Whitestone pays by the answer, and Ulrica intends to earn it. First: the full register of tunnels. 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 <= 1362; 0 <= m <= 2724.

Example 1:

Input: 779 778 1 779 88 250 176 347 280 283 743 753 161 607 209 332 618 649 327 727 98 474 76 391 532 594 58 254 416 644 147 770 613 654 45 563 386 765 505 619 131 166 258 427 126 443 695 698 204 399 264 684 49 436 155 653 291 702 413 518 661 701 431 610 159 291 355 459 290 731 308 517 714 725 265 565 45 618 448 700 411 580 512 518 519 664 328 422 159 407 413 625 278 404 149 196 92 497 13 567 72 757 599 620 389 740 238 502 279 709 336 365 305 351 628 631 480 695 132 213 238 746 55 445 350 733 155 254 641 670 615 740 551 736 550 643 273 564 467 579 255 367 461 540 355 754 350 724 467 542 415 512 149 482 9 404 309 703 296 601 201 352 213 588 70 540 268 572 129 165 366 404 168 743 200 764 553 640 230 457 173 323 291 610 621 754 479 491 316 362 79 327 92 665 668 753 186 551 181 607 130 321 14 669 224…
Output: 11

Example 2:

Input: 373 2150 1 373 56 140 144 153 167 332 115 123 106 356 159 298 19 242 63 79 12 144 133 275 37 342 191 258 119 174 42 262 273 343 293 350 12 319 18 61 189 269 69 267 122 352 179 297 227 352 180 280 61 347 19 198 11 110 196 253 21 201 182 222 119 259 65 115 156 309 65 238 168 229 33 313 182 281 10 167 120 362 86 336 14 222 127 256 109 135 180 373 145 349 155 352 191 335 90 279 59 306 1 77 134 339 156 235 139 269 117 333 90 167 152 221 136 140 202 297 6 350 260 341 279 316 211 337 7 138 15 173 179 308 16 112 272 358 21 184 75 315 39 368 44 237 295 303 103 215 226 273 272 348 63 86 34 292 175 240 211 259 92 336 18 67 88 301 62 125 111 335 159 180 142 251 93 117 323 324 227 318 72 75 243 335 156 271 111 130 315 332 127 195 146 233 282 329 257 318 36 267 2 67 197 250 86 89 9 19 265 286 147 290 14…
Output: 2

Example 3:

Input: 878 2304 1 878 14 74 491 872 154 516 88 689 236 722 139 535 61 786 173 463 189 258 28 736 210 267 193 239 450 746 51 180 268 651 273 758 155 624 204 798 3 609 154 489 225 534 92 634 72 213 47 748 286 875 79 863 622 778 306 396 186 441 516 575 101 817 106 801 339 650 425 523 799 821 53 567 123 157 754 811 95 254 248 723 40 738 171 795 52 62 594 610 108 426 3 391 7 525 257 629 32 240 323 683 49 86 31 61 329 721 27 451 300 522 8 724 205 340 87 196 571 574 10 196 483 847 103 603 402 837 103 165 155 510 275 445 113 230 459 814 228 240 776 866 468 531 375 418 76 334 12 573 72 657 406 547 244 714 191 828 112 590 391 779 325 373 118 620 23 126 633 817 48 344 241 321 181 779 90 396 82 357 72 757 36 874 666 678 332 743 96 600 196 628 98 667 131 670 129 451 431 532 199 502 357 743 415 849 72 74 601 7…
Output: 5

Constraints:

1 <= n <= 1362; 0 <= m <= 2724.

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