CT33678

The Ancient routes of Theron

MediumL4 · Loop LordAcceptance: 0.0%XP: 35

Theron inherited the apiary at the quays of Driftwood along with its curious bookkeeping system for routes. Time to make sense of it. 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 <= 1023; 0 <= m <= 2046.

Example 1:

Input: 1003 1927 1 1003 249 498 595 990 286 509 615 850 809 920 620 953 675 929 249 795 803 869 203 801 119 186 121 374 258 343 55 611 163 967 202 344 38 319 323 364 260 327 261 897 526 585 946 996 78 238 286 995 107 616 510 685 410 817 49 765 58 674 846 960 566 1001 8 222 205 367 162 744 425 897 176 819 104 138 14 914 566 715 819 926 842 969 437 973 527 600 274 373 142 453 329 391 163 843 616 618 597 854 464 599 314 954 304 917 688 903 19 954 938 944 61 266 131 748 277 935 193 503 330 982 697 771 484 774 38 716 432 516 934 960 603 911 149 360 327 937 123 701 464 758 1 251 433 579 69 249 588 741 624 841 188 836 455 565 584 930 316 527 209 382 384 506 549 707 328 596 192 691 252 814 456 710 520 774 454 793 511 672 185 589 201 998 89 474 766 770 187 921 533 903 153 663 7 132 413 927 318 595 94 717 …
Output: 6

Example 2:

Input: 575 1060 1 575 299 376 429 479 377 572 336 496 238 392 372 417 281 350 257 287 361 515 371 403 72 214 271 320 18 459 71 345 328 515 98 535 100 553 130 137 31 102 104 358 40 540 106 194 295 380 81 320 320 339 527 571 226 245 54 561 189 278 10 552 37 112 132 241 197 571 61 87 3 557 68 286 386 514 43 433 330 562 93 246 204 463 217 285 102 303 330 336 163 457 215 564 326 419 81 192 81 389 342 498 90 123 356 394 23 283 111 376 18 78 142 448 87 243 48 66 400 443 31 463 131 375 431 547 185 293 172 404 494 565 122 503 257 523 294 331 104 117 199 527 90 219 3 115 288 571 269 398 495 518 226 355 73 285 90 204 114 561 152 522 76 231 448 540 70 486 363 400 63 273 2 425 397 536 446 537 14 27 155 334 336 481 391 513 22 396 108 519 32 150 156 267 244 417 193 503 31 185 276 353 457 520 203 315 20 289 332 …
Output: 5

Example 3:

Input: 336 816 1 336 164 308 137 313 140 220 110 335 20 333 66 176 256 280 67 90 90 130 180 205 162 242 59 275 62 153 22 157 107 160 125 248 40 153 124 228 115 201 88 210 50 318 229 243 99 118 132 317 35 245 147 167 24 243 9 268 33 55 41 109 89 179 13 83 76 104 2 15 133 234 111 321 38 281 21 142 42 62 12 278 169 199 321 325 226 300 85 104 58 109 126 149 25 163 156 284 32 42 174 199 1 251 80 233 120 303 46 192 149 224 2 72 9 31 253 264 101 329 190 255 116 291 16 263 207 296 85 242 15 103 301 333 44 297 6 152 101 257 83 103 91 157 109 232 175 327 192 199 209 266 80 332 63 115 232 334 126 127 123 336 198 213 12 326 168 314 57 195 261 288 61 168 13 90 141 299 19 199 134 332 3 125 207 256 24 299 78 254 247 301 129 193 33 78 103 125 79 176 80 193 2 229 261 332 111 294 170 278 25 160 121 197 176 324 21 …
Output: 3

Constraints:

1 <= n <= 1023; 0 <= m <= 2046.

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