CT42485

The roads at Glowfen

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Deep in the lantern district of Glowfen, Mira 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 <= 1586; 0 <= m <= 3172.

Example 1:

Input: 1235 2399 1 1235 390 684 43 557 209 849 416 1153 2 687 1041 1149 774 866 1006 1107 403 1087 56 547 568 703 19 1049 462 509 548 677 257 1174 100 930 248 363 484 1139 94 657 528 1157 817 1106 758 1235 292 329 231 990 993 1150 478 570 612 613 176 461 510 1105 17 554 222 226 290 619 10 102 336 530 1046 1173 590 1179 217 720 1016 1045 144 906 155 470 762 1183 120 1050 361 500 507 1220 250 584 827 1038 501 862 138 998 89 628 145 234 95 186 689 1167 1083 1127 23 148 356 442 742 830 523 731 163 986 474 1156 1073 1076 244 471 1188 1198 24 781 941 1189 398 701 556 791 333 959 333 860 315 1112 124 341 333 743 348 915 435 468 343 550 925 1072 1030 1188 891 1105 221 1206 43 1107 805 879 521 821 95 355 494 692 729 1232 517 844 71 589 604 959 59 921 277 835 113 771 652 942 124 551 12 1030 513 767 892 927…
Output: 3

Example 2:

Input: 1490 1489 1 1490 1314 1365 85 120 90 147 314 837 1113 1293 734 852 245 828 140 298 341 1437 680 1124 194 1481 756 871 8 413 766 968 334 457 130 1196 923 1363 490 847 652 1311 133 646 155 1409 232 706 479 505 377 474 264 1240 1015 1442 504 1459 55 458 328 739 515 1463 513 1383 1226 1258 181 663 251 627 1325 1332 921 1285 522 766 609 1298 72 1279 442 596 59 1369 403 706 1046 1390 1460 1475 918 1430 494 1178 835 1154 1227 1238 1061 1127 147 733 619 703 964 1020 141 146 711 1325 895 1106 296 827 9 1053 68 1180 244 807 974 1289 449 1024 786 1130 383 1195 115 975 167 934 208 864 233 1323 451 927 363 489 746 1230 500 951 173 902 128 744 491 691 420 1081 689 822 473 1275 359 371 402 697 219 310 115 1247 385 597 93 594 862 1323 54 333 246 899 366 813 1045 1393 234 830 319 1088 66 1235 1233 1428 918…
Output: 11

Example 3:

Input: 755 1902 1 755 450 668 62 323 19 662 611 726 18 363 160 700 8 148 62 127 360 535 404 658 314 424 170 622 191 693 638 724 438 529 14 439 108 589 401 544 123 343 280 743 124 575 5 211 21 268 506 570 34 429 474 476 581 657 365 377 358 714 79 176 399 582 444 507 644 680 72 561 529 601 657 748 514 680 73 598 343 645 185 643 231 497 125 234 112 698 164 702 139 160 102 364 371 735 209 483 314 331 214 335 63 296 348 417 693 748 209 294 172 365 454 576 245 670 113 504 377 418 479 629 391 395 11 346 252 634 103 655 544 749 112 184 352 654 333 646 264 541 163 401 492 580 169 567 706 721 33 377 214 264 243 635 44 370 170 238 45 214 84 461 207 375 539 612 231 717 262 644 117 546 388 701 261 618 259 438 36 256 132 570 295 739 277 406 370 459 227 551 319 336 103 249 427 565 100 609 122 422 48 178 164 287…
Output: 6

Constraints:

1 <= n <= 1586; 0 <= m <= 3172.

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