CT46828

Petra and the Fewest Hops

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

The council of the cliffside roost of Stormrest pays by the answer, and Petra intends to earn it. First: the full register of routes. 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 <= 2472; 0 <= m <= 4944.

Example 1:

Input: 1825 1824 1 1825 1020 1249 1301 1742 683 1586 287 319 591 1411 1527 1718 972 1510 387 1556 33 720 81 1810 1088 1421 614 1505 438 585 190 1409 508 1014 811 1823 800 1501 832 1256 416 609 573 1423 1461 1707 271 1676 1229 1631 894 1109 900 1484 121 791 1028 1257 169 343 437 665 1323 1675 1464 1493 42 921 925 984 198 795 369 1271 1018 1695 917 1401 1043 1736 385 1203 1015 1204 185 1706 905 1424 1643 1667 142 839 765 937 334 1146 150 1074 795 1514 708 1368 157 287 162 1252 25 1121 1606 1688 676 1610 1073 1111 183 206 144 598 1125 1209 567 1469 140 840 474 1728 432 1147 571 1176 110 206 1417 1633 649 1213 501 825 231 423 595 1522 552 871 36 1153 635 869 1076 1428 164 1283 107 1159 35 527 1413 1532 644 821 1709 1760 448 1075 891 1631 647 1575 397 1226 297 1139 1282 1471 1170 1658 869 1552 1047 13…
Output: 15

Example 2:

Input: 524 3617 1 524 31 319 403 436 262 389 189 447 25 32 164 263 34 507 270 499 423 512 440 451 241 402 120 295 101 341 2 133 194 422 459 485 124 129 62 321 151 293 296 359 156 508 93 114 241 493 127 488 100 224 3 111 83 267 239 297 67 273 95 189 137 437 54 251 391 452 55 71 61 77 301 413 73 274 143 319 32 275 426 451 7 521 258 274 222 397 522 524 362 389 62 111 469 496 121 275 115 181 68 364 211 248 121 285 22 521 146 213 270 399 2 238 213 345 41 282 55 421 181 458 388 466 17 231 329 353 292 304 153 417 197 457 201 332 58 191 408 472 22 423 47 465 8 395 82 386 290 459 232 466 217 331 43 285 392 424 140 214 273 416 73 122 106 352 80 413 37 202 44 466 144 323 239 458 140 286 112 169 83 329 205 510 18 122 79 339 271 473 114 255 381 493 64 149 270 361 383 491 66 174 28 512 12 15 97 246 173 374 357…
Output: 3

Example 3:

Input: 1063 1319 1 1063 228 376 274 376 219 469 204 661 28 353 396 1055 618 703 308 697 97 930 147 358 50 731 340 548 113 1054 250 437 497 978 38 365 784 900 371 544 479 756 22 372 17 538 306 661 1001 1035 710 821 442 539 207 339 681 1011 63 986 72 268 332 504 424 853 930 1031 54 227 85 633 582 1010 678 951 582 860 471 546 109 116 130 975 926 1000 264 963 99 374 512 932 252 414 134 181 88 589 428 1039 232 1024 266 686 370 1021 394 493 45 573 630 887 177 404 778 971 505 730 546 1012 71 609 18 732 403 675 66 952 532 1056 192 498 143 955 965 1062 664 908 778 920 70 774 261 689 1 839 488 867 578 852 423 949 120 690 325 926 408 615 347 917 699 761 388 627 381 452 580 896 80 157 298 1047 734 823 6 796 845 943 150 459 627 779 69 722 189 1029 494 711 376 800 182 932 810 932 8 930 1017 1044 389 447 275 53…
Output: 7

Constraints:

1 <= n <= 2472; 0 <= m <= 4944.

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