CT49653

Jatin's bridges Fewest Hops

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Morning light hits the savanna camp of Amberplain as Jatin unrolls the day's manifest of bridges. The tally will decide the next shipment. 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 <= 1683; 0 <= m <= 3366.

Example 1:

Input: 1583 2520 1 1583 247 1053 481 542 926 1464 781 1458 133 574 83 1495 690 1085 1376 1563 682 1382 1190 1291 569 1088 123 845 207 1545 98 1346 412 481 339 829 388 774 366 672 497 930 931 1223 1190 1445 262 1419 879 1322 993 1235 556 814 973 1484 379 793 149 1276 933 1197 80 1065 544 1555 478 1369 319 1350 101 318 182 1496 945 1347 157 623 1462 1535 1117 1168 121 448 1454 1544 483 1519 885 1179 649 940 1067 1122 411 1359 258 486 678 749 160 471 256 703 868 909 342 852 725 1118 655 1156 1040 1072 1507 1534 520 809 12 115 464 471 341 1234 461 1091 1263 1550 367 881 187 438 374 1191 496 963 663 1429 88 1024 106 1010 278 753 751 1159 744 1433 443 1083 1008 1055 59 408 350 1438 462 1224 437 547 49 627 499 1124 1079 1273 1197 1297 1044 1439 249 1332 421 523 130 1464 877 991 848 961 315 1303 1152 155…
Output: 7

Example 2:

Input: 894 1170 1 894 140 440 543 797 548 736 258 865 141 198 197 249 405 516 356 788 567 731 248 812 43 827 599 787 212 793 624 711 103 583 186 834 294 398 291 850 85 827 72 321 329 398 328 788 43 520 126 812 184 394 309 774 260 685 222 359 118 265 6 199 562 784 442 551 479 864 465 838 247 304 270 753 725 799 83 876 333 839 394 844 182 344 19 807 20 207 189 535 646 766 308 754 338 733 654 820 255 755 123 684 161 639 12 137 391 603 393 868 476 808 252 283 125 671 587 838 103 560 447 783 471 825 226 417 39 759 63 555 333 346 45 422 52 180 4 808 545 831 652 857 44 375 209 361 480 619 329 678 120 327 608 809 854 856 95 570 34 851 39 384 598 721 11 230 228 313 169 312 334 792 330 627 198 200 189 218 493 799 50 450 613 824 169 734 76 638 447 580 49 625 78 627 3 265 332 863 484 679 504 529 330 392 103 …
Output: 5

Example 3:

Input: 198 1758 1 198 88 97 68 147 36 170 90 119 98 193 19 141 1 89 164 165 15 69 104 191 90 154 141 197 114 147 38 53 61 98 23 143 24 179 86 184 19 121 90 146 117 178 16 197 66 194 85 198 20 74 16 58 51 58 25 184 64 84 88 102 25 49 175 180 22 45 143 156 156 166 57 85 53 118 5 98 18 144 59 109 144 195 134 192 139 195 103 197 124 151 90 125 13 82 4 190 136 180 84 143 39 87 87 134 11 125 19 73 114 178 3 185 93 185 2 194 4 117 28 187 115 182 51 77 18 66 107 109 33 116 92 185 112 160 111 173 41 192 53 70 64 180 112 138 9 96 100 144 13 179 12 129 1 98 1 127 43 101 71 193 114 165 10 100 17 30 113 147 72 99 107 154 55 179 147 163 26 99 21 112 2 27 35 62 83 103 46 196 64 163 77 164 42 185 26 36 3 119 65 152 92 164 50 164 9 92 73 79 43 131 12 33 147 151 137 197 37 100 95 190 103 110 137 187 52 79 71 94 82…
Output: 2

Constraints:

1 <= n <= 1683; 0 <= m <= 3366.

Loading...
Test Cases:No test cases
No test cases available.
Jatin's bridges Fewest Hops - MEDIUM Coding Problem | CodeTikki