CT51248

The roads at Luminar

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

The harbor bell rings at the crystal caves of Luminar; Ivo weighs the day's roads manifests and starts the calculations. 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 <= 3371; 0 <= m <= 6742.

Example 1:

Input: 3032 3871 1 3032 1864 2901 367 584 632 1020 1907 2271 294 2774 855 1144 2599 2969 1262 1273 1614 2993 1022 1330 2202 2875 1827 1889 1546 1934 1513 2287 2011 3003 1425 2468 1719 2758 1684 2879 1234 1630 3 2232 573 1113 2380 2864 1471 2018 108 438 2223 2400 23 2443 202 1065 835 1655 4 2699 2505 2702 1076 1954 795 1845 274 1415 760 1605 144 830 72 566 1 194 197 2385 516 2479 915 1911 1061 2590 355 1559 735 1695 1320 2130 1831 3023 1368 1728 290 880 580 2249 2743 2962 813 2370 1331 2071 2572 2733 767 1023 26 1183 1364 2821 2309 2839 1075 1257 281 889 382 2915 1603 2509 1959 2292 744 1171 1354 2683 431 2258 1694 1800 550 2422 706 1821 715 1603 1532 2605 124 788 2552 2948 774 2316 431 1289 601 1451 1322 1676 805 1635 1151 2837 2120 2609 1647 1824 2063 2963 2654 2758 47 807 1320 2987 125 501 444 …
Output: 14

Example 2:

Input: 1327 4012 1 1327 67 419 648 842 865 1029 1070 1171 309 863 426 1128 173 962 502 1267 264 792 630 946 954 973 1040 1254 874 1141 865 1183 163 893 192 405 681 1055 242 1265 514 1276 295 671 601 1158 251 284 914 1255 177 671 38 1317 719 1214 809 811 883 1199 976 1093 326 481 5 461 92 366 501 695 475 1013 727 1172 707 1146 118 1045 285 1260 453 1165 44 1211 1215 1242 156 353 329 991 1072 1266 736 797 466 613 1128 1137 364 1074 541 1047 510 641 600 955 292 1106 1183 1275 329 382 343 582 76 655 101 781 627 635 942 1019 933 1223 558 968 437 1115 472 1189 282 453 1039 1163 173 1318 787 1275 244 1193 268 711 1135 1325 15 1002 403 1083 161 565 263 1088 210 1298 720 901 562 1296 222 308 381 1269 745 1012 136 857 206 925 164 396 103 826 663 733 397 1030 721 1175 1240 1276 922 1110 129 569 860 919 804 …
Output: 4

Example 3:

Input: 539 3321 1 539 378 412 45 223 149 445 54 387 32 419 312 524 172 332 33 203 39 468 247 335 55 449 368 369 245 520 100 104 300 537 130 384 67 133 105 130 144 453 219 495 377 401 171 447 174 401 93 365 326 458 136 353 374 474 66 270 75 415 75 426 76 117 78 90 169 410 429 432 1 325 67 108 95 242 97 118 66 376 285 393 344 486 235 535 124 433 33 436 16 386 70 205 247 490 202 257 50 264 341 474 215 492 270 356 178 216 95 393 303 414 214 326 258 539 211 340 215 421 132 147 17 477 95 500 11 190 189 192 18 476 282 530 86 405 200 243 371 460 209 527 218 341 163 320 177 198 6 368 25 147 203 280 297 463 52 305 219 390 4 148 112 276 277 494 154 402 75 370 295 506 93 107 236 406 26 526 386 395 305 352 55 214 110 130 165 302 33 374 163 380 160 186 246 391 53 516 123 535 195 369 405 406 227 269 400 442 434…
Output: 3

Constraints:

1 <= n <= 3371; 0 <= m <= 6742.

Loading...
Test Cases:No test cases
No test cases available.
The roads at Luminar - MEDIUM Coding Problem | CodeTikki