CT50668

Zaid Counts the roads

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

The harbor bell rings at the mushroom groves of Fungaldeep; Zaid weighs the day's roads manifests and starts the calculations. 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 <= 3359; 0 <= m <= 6718.

Example 1:

Input: 3206 4947 1 3206 2318 3166 1838 2013 1517 2148 583 882 2101 2144 1076 1337 512 619 2262 2279 614 721 1087 1460 2401 2454 758 1346 2997 3100 1973 2509 702 1272 1432 2525 1035 3028 672 1320 1183 3028 1324 2987 124 1254 1245 1876 1412 2279 451 1702 1564 2356 2503 2727 738 3130 2157 2569 1931 2562 2311 3070 383 962 1601 2535 1079 2748 63 2595 102 1424 922 2014 1303 1743 1241 2048 859 1887 1943 2671 1892 2233 1605 1660 2065 2840 553 1176 753 1328 685 1879 290 1174 1616 2897 1007 2726 481 2913 79 432 996 2408 2651 2868 83 346 491 1869 2607 2816 1488 2217 196 1151 304 2976 629 1990 1320 2874 1693 2052 2418 3067 1489 2102 42 3152 1141 3187 984 2848 523 2519 970 1604 583 2744 583 1372 2167 2480 602 1150 407 435 2692 2868 666 788 282 2372 139 2131 1692 1700 743 3002 796 2896 1204 1381 1815 2115 1886…
Output: 10

Example 2:

Input: 1429 4959 1 1429 1018 1071 495 1147 437 808 51 1036 329 907 129 134 247 671 415 918 216 1160 1107 1416 1147 1307 192 879 714 920 808 815 325 717 225 1287 175 946 141 349 835 1136 338 736 1197 1243 43 282 487 975 158 906 685 1043 508 865 354 674 416 1129 272 1003 74 320 296 371 999 1005 1134 1307 112 1351 1006 1232 15 610 285 516 892 1284 481 797 15 45 1053 1333 103 130 237 990 456 580 12 454 201 981 362 466 38 148 924 975 724 842 114 1017 684 1106 1098 1173 739 893 229 245 411 753 225 486 945 1149 409 655 1201 1392 641 993 173 412 849 1178 369 949 44 1307 719 911 128 1099 439 885 1187 1281 5 610 767 1355 609 675 969 1088 271 886 36 569 313 644 621 689 842 1037 720 845 643 1290 783 1092 958 1359 160 819 551 1147 35 1230 307 1198 714 1179 541 1056 601 848 684 947 964 1067 273 983 385 1078 40…
Output: 5

Example 3:

Input: 611 1731 1 611 9 295 286 583 69 255 61 429 57 208 196 476 47 161 64 408 242 403 56 547 196 556 184 439 483 507 116 446 139 354 247 488 522 583 187 598 2 160 337 360 373 406 101 469 153 504 40 81 153 259 192 227 426 584 108 453 98 518 212 340 240 249 106 471 163 318 343 374 143 571 492 579 284 587 401 473 551 574 407 609 26 591 526 559 278 294 151 459 126 174 420 563 318 373 112 287 239 503 315 342 70 225 317 570 42 364 327 497 390 609 139 550 141 595 126 460 431 545 14 516 338 508 143 586 353 477 66 438 200 439 219 252 144 467 232 474 122 334 77 392 52 334 83 400 360 431 31 496 210 434 112 132 353 392 318 382 122 428 233 445 119 257 45 93 16 29 28 604 280 344 250 387 105 246 114 302 153 459 207 270 316 431 118 591 39 367 154 609 331 547 86 510 243 389 487 498 88 143 168 608 68 210 481 552 …
Output: 2

Constraints:

1 <= n <= 3359; 0 <= m <= 6718.

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