CT48842

The Fewest Hops of Selene

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

The council of the moonlit lagoon of Selene pays by the answer, and Viktor intends to earn it. First: the full register of bridges. 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 <= 2012; 0 <= m <= 4024.

Example 1:

Input: 1566 3568 1 1566 81 392 817 1528 462 1058 969 1315 34 728 140 584 519 1059 151 755 49 98 491 1079 522 1364 99 115 777 1329 684 1196 506 1301 919 1411 365 1103 1251 1453 64 516 722 1003 855 1213 445 1554 81 503 1100 1553 120 981 901 1173 133 469 420 770 805 1537 357 1450 93 430 204 561 56 219 201 518 380 768 816 1235 346 1118 920 1251 966 1388 365 643 49 1399 55 1239 373 760 37 187 925 1339 403 1481 648 971 1476 1519 424 1243 1188 1335 427 826 498 1459 425 1509 127 362 421 1464 478 1446 6 1299 1298 1351 169 1322 253 613 710 799 1472 1498 453 1409 236 1240 126 1410 791 1038 423 1188 426 831 226 899 168 833 26 372 997 1078 825 1067 656 1232 132 948 1058 1251 123 558 212 900 786 1463 1098 1434 1272 1494 967 1031 1319 1321 194 690 415 696 274 1357 696 808 301 926 104 355 263 324 249 1508 535 59…
Output: 6

Example 2:

Input: 1897 1896 1 1897 169 731 366 638 862 1035 423 1053 1330 1641 105 1830 1108 1458 272 1631 933 1760 859 1232 1637 1677 1594 1658 951 1224 182 1688 478 1002 647 1830 91 1581 456 987 646 1588 782 1393 78 1481 1480 1514 593 1458 90 614 795 1117 467 1335 197 1865 1386 1412 638 1779 207 990 1333 1530 110 939 1452 1501 1582 1646 537 1627 1332 1390 941 1129 1349 1793 762 1120 1668 1678 1279 1587 26 1124 457 859 541 1715 36 1546 668 1641 1146 1263 449 801 604 1007 293 1431 688 1223 392 831 175 258 757 1286 385 950 681 1818 1151 1567 369 1627 800 1152 10 1418 1501 1569 309 1265 1079 1511 469 1709 1103 1295 68 861 607 1419 27 383 457 912 269 472 627 1803 164 798 530 1456 1442 1726 129 1877 480 491 759 1380 143 1419 166 838 131 1187 251 1239 354 521 3 1428 13 1416 133 1402 1312 1783 63 1661 90 988 1631…
Output: 10

Example 3:

Input: 587 2441 1 587 83 196 318 489 90 476 23 373 118 152 128 186 76 200 338 452 350 521 179 547 17 86 84 557 127 233 95 128 501 566 63 94 219 472 372 429 284 436 307 438 254 424 213 232 157 455 448 529 528 556 359 473 51 121 273 392 8 417 46 231 31 276 336 498 422 560 9 400 410 453 386 525 102 431 13 498 43 437 316 539 128 155 81 479 291 458 51 230 153 515 108 484 175 394 189 273 197 306 258 394 1 465 139 193 116 259 65 266 119 224 44 228 80 488 65 542 11 490 236 479 272 504 12 465 521 540 103 126 43 73 246 525 123 160 161 562 201 566 47 59 512 584 543 567 224 357 187 299 129 455 272 411 271 446 320 554 308 362 84 369 373 381 91 259 85 356 162 565 381 478 114 388 147 490 234 523 120 177 415 516 110 444 52 319 428 504 180 459 78 302 222 490 26 233 155 427 391 454 308 490 517 535 89 519 178 370 8…
Output: 2

Constraints:

1 <= n <= 2012; 0 <= m <= 4024.

Loading...
Test Cases:No test cases
No test cases available.
The Fewest Hops of Selene - MEDIUM Coding Problem | CodeTikki