CT54370

Jade tunnels Fewest Hops

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Sailor inherited the aviary at the copper works of Verdigris along with its curious bookkeeping system for tunnels. Time to make sense of it. 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 <= 3407; 0 <= m <= 6814.

Example 1:

Input: 229 5006 1 229 167 208 26 103 39 220 53 109 168 194 27 191 120 158 128 170 23 108 101 203 115 198 73 203 116 191 152 156 57 171 69 112 104 222 59 200 74 105 180 203 72 224 30 108 110 200 5 111 91 144 31 188 35 38 128 154 43 128 28 127 224 229 156 199 134 146 108 114 60 120 18 179 14 226 70 85 17 64 34 60 108 122 24 88 11 101 7 77 86 170 155 221 38 223 20 206 146 174 31 84 135 150 127 154 42 130 89 146 143 176 38 213 87 172 56 123 76 168 48 107 19 163 53 212 39 65 119 217 19 102 123 182 37 197 84 206 74 190 111 170 24 200 65 95 48 59 33 159 45 155 6 146 42 190 15 41 2 87 53 60 85 222 51 228 34 148 46 99 26 63 54 144 43 86 2 159 19 24 68 116 121 170 20 29 153 186 33 70 93 218 157 186 6 14 16 99 2 119 44 84 196 222 14 185 83 202 35 185 161 165 112 219 97 207 133 141 150 165 130 187 64 122 53 …
Output: 2

Example 2:

Input: 3147 3146 1 3147 1269 2927 1088 1305 246 2866 769 2719 2343 2646 905 2813 581 3097 2001 2370 3 3093 348 1866 667 1564 117 2430 1756 2492 1437 2243 840 1636 371 736 1698 2423 402 2722 305 1883 374 2638 1027 1780 7 2793 205 906 545 2493 460 1780 1407 1679 2194 3040 272 778 1559 1940 759 2624 896 1407 597 1330 96 425 85 2494 97 1101 8 1352 1206 2739 405 2266 262 2116 1574 2716 1147 2177 2979 3014 374 501 1152 3024 1225 2809 1550 2624 368 2238 214 1538 1758 2096 180 2626 1145 2754 1190 2654 2411 2645 3062 3108 892 2493 1865 2778 847 2126 2826 2846 638 3066 603 1156 525 1425 76 199 1220 1559 2306 2916 480 3013 1806 2713 261 1696 259 594 74 677 1246 1272 1714 1906 306 926 1445 2785 543 1148 520 1702 1275 2045 2180 2194 149 2426 1505 3117 406 455 1780 2833 291 2406 314 1056 2007 2429 2193 2866 31…
Output: 18

Example 3:

Input: 2611 3604 1 2611 725 1359 248 1441 213 1477 105 1220 383 2485 241 1462 8 106 358 2218 2100 2236 576 948 181 2093 308 2220 1963 2059 186 561 1421 1515 656 873 437 690 413 2373 1034 2517 593 1897 686 1800 868 1675 320 1599 1740 2023 1151 1733 2140 2406 373 1106 881 1543 1404 2055 465 2464 1509 1531 217 1804 1828 2082 1579 2320 976 2490 475 1999 1847 1911 150 1744 611 1945 892 1216 504 2221 710 2582 349 2022 1693 2423 386 925 322 1325 1340 2194 2223 2361 1856 2292 463 2330 611 1372 1069 1699 1401 1421 202 727 517 2552 1283 1374 379 2301 1688 1861 676 1387 822 1888 518 563 1340 2305 507 1276 1487 2410 558 1798 124 2549 1044 2157 208 792 1558 1903 518 2342 420 1231 868 1117 19 584 1899 1953 368 1041 1638 2444 330 2530 389 879 1933 2437 2346 2378 736 1774 928 1960 1094 1261 1156 1970 2 1143 1896…
Output: 7

Constraints:

1 <= n <= 3407; 0 <= m <= 6814.

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