CT52255

Dev and the Radiant canals

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

At the otter slides of Sleekwater, Dev records each canals in a worn leather ledger. The guild wants answers, not guesses. 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 <= 2426; 0 <= m <= 4852.

Example 1:

Input: 526 3762 1 526 13 351 220 255 76 299 100 197 134 190 6 242 16 487 10 230 437 488 202 431 183 248 240 378 215 313 251 348 120 481 48 447 173 239 225 461 102 504 121 483 199 323 180 379 242 340 220 524 268 330 142 513 312 388 156 192 46 105 375 461 38 241 11 355 126 161 81 419 175 321 36 319 507 508 439 471 118 269 271 319 302 393 197 524 129 191 65 92 14 521 120 223 61 524 333 502 332 370 343 463 250 453 21 386 20 129 295 452 120 392 8 402 151 277 18 369 148 418 97 447 23 79 260 487 51 73 235 421 296 456 45 67 62 495 136 378 293 373 82 134 413 490 33 503 189 379 57 204 406 485 254 402 188 452 275 322 31 251 36 450 48 375 413 517 34 294 4 51 100 127 239 400 285 324 24 172 208 352 257 508 125 127 57 177 47 382 165 384 83 187 119 504 2 183 61 162 277 350 97 477 347 409 292 452 427 435 48 446 8…
Output: 3

Example 2:

Input: 2061 3782 1 2061 1377 1693 329 765 315 1478 804 1936 364 1368 1262 1285 347 1881 532 2034 737 1627 501 1391 84 1815 413 930 1477 1590 200 802 533 1229 698 850 986 1124 714 1340 1268 1391 215 1269 1095 1725 365 433 1002 1038 156 1640 614 1048 666 902 1119 1616 1248 1788 148 502 1052 1370 820 1068 559 2040 625 993 946 1898 353 486 953 1015 1581 1672 22 1475 463 1937 125 708 546 1106 104 1975 24 1218 1312 1726 1060 1670 496 1404 238 1026 899 1654 583 1792 214 1723 146 1681 1004 1194 1623 1648 851 885 273 1748 1088 1186 568 1706 172 616 253 1878 451 1922 727 1913 181 368 603 2023 180 191 1094 1386 660 1872 131 807 1178 1543 1131 1772 959 1356 629 1454 722 1673 670 698 1331 1776 81 1144 1008 1601 1038 1586 637 1045 781 1136 803 1864 540 847 1841 2061 687 1231 359 704 558 1248 520 2038 987 1370 …
Output: 5

Example 3:

Input: 1555 4363 1 1555 413 1508 146 1029 759 883 582 1545 589 807 74 945 127 1081 236 310 31 716 418 713 1209 1290 276 1203 743 1401 856 991 87 817 103 561 639 1355 45 148 1012 1421 363 444 71 404 635 777 532 1483 724 866 147 284 568 1145 184 1312 930 1011 184 1529 229 1420 1310 1470 900 1226 83 445 1267 1529 973 1197 562 953 85 260 381 533 750 1135 1145 1339 830 1407 841 1168 242 505 248 1114 87 1456 3 296 242 281 452 631 886 1331 43 1054 1467 1531 749 1067 472 626 124 264 717 895 138 988 65 957 347 1023 549 721 359 1373 651 1321 966 996 975 1021 451 980 1161 1358 751 1502 608 1311 144 1143 109 116 102 530 53 1074 888 940 491 976 853 1278 25 1143 1254 1552 823 1435 97 492 427 1074 157 844 761 777 450 960 85 134 325 665 756 1348 828 1337 841 1270 792 1070 502 942 3 1162 1344 1415 1122 1249 614 1…
Output: 5

Constraints:

1 <= n <= 2426; 0 <= m <= 4852.

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