CT34566

The Fewest Hops of the Misty roads

MediumL4 · Loop LordAcceptance: 0.0%XP: 35

Deep in the gull cliffs of Screech Point, Scribe studies rows of roads entries. One clean number will settle the guild's oldest argument. 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 <= 1743; 0 <= m <= 3486.

Example 1:

Input: 1481 1843 1 1481 117 807 357 1169 459 927 99 168 515 739 384 1475 1412 1419 396 826 337 1292 298 357 1031 1276 19 897 800 1045 619 1354 1140 1160 227 1232 1024 1413 520 603 81 1264 340 749 1063 1369 279 1245 255 728 407 940 313 408 877 1008 1287 1315 1223 1303 483 925 4 375 171 446 811 1375 1116 1329 809 1147 703 1446 718 1472 620 1050 345 434 1258 1381 1020 1068 143 1061 185 710 476 1275 28 587 57 1137 1319 1454 348 1359 693 1131 567 756 483 645 404 1343 98 1418 663 1193 798 1127 416 1285 423 1225 400 586 959 1324 1074 1298 401 1316 1273 1455 174 644 269 414 27 1364 34 597 272 1036 559 1044 817 978 365 461 163 1333 436 1129 1080 1375 209 1307 758 760 826 1148 162 1045 495 802 649 1263 299 1192 120 762 692 728 56 648 172 259 541 894 952 1187 610 1015 976 1193 1159 1372 362 913 997 1301 584…
Output: 11

Example 2:

Input: 166 2832 1 166 26 27 32 34 8 66 74 161 5 75 10 127 36 128 91 161 92 116 116 142 42 136 45 127 31 130 66 97 26 86 36 72 11 154 13 16 100 153 1 121 138 161 43 143 25 67 33 154 66 93 124 140 11 144 108 157 80 145 117 132 12 93 85 145 27 42 67 152 117 134 85 128 74 79 11 79 22 92 20 140 40 138 36 41 114 144 89 90 60 107 32 113 135 163 105 150 73 130 126 157 1 25 51 93 42 132 135 150 27 100 93 94 50 137 70 81 17 45 35 119 55 88 103 114 85 141 25 117 59 60 9 29 13 143 118 161 39 78 1 134 34 57 40 90 127 142 45 69 100 142 37 147 76 85 19 41 49 149 72 165 109 141 48 159 83 105 86 123 4 55 82 153 148 155 102 141 107 149 78 114 10 99 14 105 69 152 139 144 74 121 111 133 43 99 53 122 53 151 70 113 49 112 72 81 154 156 21 75 67 76 54 103 22 45 136 166 46 66 30 136 27 137 84 93 10 15 119 139 84 126 50 …
Output: 2

Example 3:

Input: 1416 2169 1 1416 1182 1279 764 1199 332 444 437 521 167 541 565 859 329 1183 499 1154 462 683 74 843 549 1321 864 1210 551 922 23 801 1229 1299 151 930 87 93 591 1325 467 722 83 747 1108 1194 992 1151 852 1132 254 1354 50 597 221 1203 145 692 502 1300 804 1012 1095 1402 758 1337 950 1403 374 621 207 812 1224 1306 144 1002 173 1107 369 883 495 925 384 751 1357 1403 846 1304 544 913 1083 1195 83 1164 1051 1122 198 730 378 821 315 973 113 1190 369 1133 1193 1411 843 1130 350 506 561 1046 341 1162 927 955 910 1381 117 848 801 936 137 151 118 191 115 663 677 1005 498 894 686 1162 996 1180 724 983 907 1218 618 1295 500 1283 711 926 6 1357 371 496 220 382 409 620 837 939 408 1220 31 946 966 1174 659 1225 1001 1226 452 1155 381 1246 997 1133 154 221 1245 1391 1233 1410 90 1410 177 409 209 1102 124…
Output: 7

Constraints:

1 <= n <= 1743; 0 <= m <= 3486.

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