CT36622

Warden Counts the corridors

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Warden runs the loft at the crystal caves of Luminar. Today the books show a list of corridors, and the numbers must be worked out before sundown. 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 <= 3028; 0 <= m <= 6056.

Example 1:

Input: 2609 2608 1 2609 46 2285 312 2302 1187 1289 122 1817 99 1477 1936 2273 1187 2157 77 1148 1227 2511 535 1984 580 963 1808 1971 495 2264 480 632 898 1370 804 1797 1248 2490 1013 2609 553 1113 617 2140 1839 2311 340 870 370 860 891 2519 1491 1671 484 1765 696 1403 1723 2442 9 155 102 157 12 1298 205 467 546 1404 527 1381 1211 2595 1168 1833 35 1688 747 1599 1962 2464 68 1081 33 1806 1403 1758 2534 2604 740 1527 1387 1805 1779 2049 861 2129 699 1051 1015 2096 954 2012 755 1813 42 2027 1732 1931 1781 1829 1669 2347 1742 2000 263 1426 489 1412 728 1584 968 1496 1049 1695 418 1156 44 826 1463 2050 425 780 798 1966 699 841 282 1949 42 1654 552 1215 948 2594 1485 2528 432 2005 320 558 599 1943 1269 2461 959 1285 652 1188 2166 2448 159 199 936 2467 1014 1185 1437 2355 1184 2483 1838 2428 1738 2441 7…
Output: 10

Example 2:

Input: 1319 3182 1 1319 783 786 196 201 795 1008 921 1129 875 1225 12 640 533 1026 678 1238 400 680 529 868 48 655 599 1157 288 1031 14 1034 301 425 965 976 597 767 244 329 641 663 371 406 1177 1298 500 1053 270 726 861 1196 945 1147 133 382 92 1166 233 548 347 1175 330 651 249 703 381 604 235 1226 986 1304 921 1164 461 467 37 625 28 992 602 963 660 732 475 958 9 30 358 451 137 1302 106 1062 385 771 330 704 322 969 186 962 178 614 366 1112 371 537 151 798 80 1216 845 999 942 1146 157 1206 801 1264 442 856 152 1315 139 710 33 770 115 1243 493 580 376 1202 264 440 397 1199 328 994 7 462 161 476 418 837 920 932 1198 1308 187 660 325 1053 718 914 639 677 179 599 376 1081 38 949 235 962 1090 1291 863 1017 1084 1095 15 438 205 395 212 986 531 591 80 478 656 1128 501 829 1107 1267 750 812 146 439 464 53…
Output: 3

Example 3:

Input: 460 5078 1 460 279 328 76 375 96 99 337 443 174 229 212 261 361 406 34 59 67 304 197 434 88 295 50 285 342 360 143 333 156 382 261 425 106 272 412 450 234 277 41 349 48 346 97 181 154 361 102 244 221 357 383 453 158 303 389 410 27 148 157 204 353 455 225 423 46 421 387 401 13 291 174 449 237 294 216 375 403 415 282 323 34 367 283 362 421 448 120 405 23 337 148 352 43 232 6 322 82 454 74 154 39 374 61 388 152 260 4 15 108 149 307 452 296 420 99 319 39 392 147 187 18 351 24 303 68 324 338 372 285 450 142 247 117 383 111 323 240 444 70 156 59 134 88 443 176 401 141 420 147 427 145 332 303 366 141 372 27 198 322 363 191 404 32 43 128 450 260 359 127 191 95 442 261 428 182 342 77 454 134 417 88 361 28 325 48 449 21 229 276 332 36 358 2 214 56 412 172 331 59 144 237 276 34 350 116 418 103 117 43…
Output: 3

Constraints:

1 <= n <= 3028; 0 <= m <= 6056.

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