CT44045

Squire's Jasper tunnels

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

At the jade shrine of Serpentis, Squire records each tunnels in a worn leather ledger. The guild wants answers, not guesses. 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 <= 2857; 0 <= m <= 5714.

Example 1:

Input: 72 2556 1 72 3 22 7 61 10 60 13 62 49 70 18 65 29 68 25 64 28 53 17 19 11 33 34 39 25 41 19 59 35 54 38 43 10 29 9 46 29 66 9 26 21 67 6 9 27 43 7 8 29 59 15 42 48 70 22 32 17 31 23 29 10 12 19 57 9 20 64 67 19 64 2 41 16 56 13 20 16 36 12 46 11 65 12 29 12 18 33 37 22 56 35 61 47 72 21 62 33 63 55 61 34 51 58 62 9 56 13 28 2 72 17 44 9 28 46 57 7 22 1 43 15 65 52 63 19 36 48 64 8 35 1 37 30 42 21 23 2 68 19 28 28 31 9 57 24 56 1 56 10 48 31 61 14 65 35 65 6 15 34 46 39 53 33 55 47 48 45 50 43 53 10 42 49 54 34 62 5 54 18 53 5 48 9 72 9 45 48 58 2 30 10 28 45 63 22 39 61 68 22 45 37 39 8 44 13 26 13 65 3 21 61 64 12 55 7 39 19 49 31 45 1 66 60 61 35 59 32 62 31 50 49 71 5 26 25 28 11 59 8 69 2 12 20 22 33 62 25 40 36 51 67 69 26 42 7 32 32 58 7 14 19 27 49 68 48 55 3 39 31 43 16 61 14 70 1…
Output: 1

Example 2:

Input: 113 3468 1 113 55 70 7 18 12 37 67 80 74 87 12 99 3 65 4 105 40 56 50 89 19 110 35 105 41 99 4 79 36 65 18 101 4 37 8 44 21 54 3 33 24 112 20 99 20 87 21 111 14 46 34 91 8 94 27 46 7 26 70 77 18 62 73 109 72 92 85 104 13 82 73 88 30 110 6 85 1 30 38 47 54 104 56 83 38 55 35 39 47 93 91 95 85 102 10 13 38 71 23 43 55 93 102 104 4 76 16 65 55 101 7 54 13 45 44 67 2 73 94 99 58 91 39 58 12 57 83 110 21 57 36 61 36 44 17 83 15 72 6 27 51 96 48 54 35 64 2 9 11 25 59 93 60 72 26 45 24 109 59 104 6 31 10 58 13 88 18 45 76 102 33 46 15 51 23 53 26 38 40 76 7 87 33 73 16 55 6 73 6 47 67 71 3 27 21 45 94 100 75 94 30 62 80 94 82 110 91 92 86 96 11 64 61 96 17 42 49 108 2 108 32 82 87 92 7 23 37 106 30 79 52 71 84 104 53 97 19 104 23 79 55 83 10 54 16 54 53 80 33 90 3 49 108 111 31 49 17 105 14 30 8 …
Output: 1

Example 3:

Input: 1268 5659 1 1268 871 1266 288 941 619 841 460 1002 61 1001 543 1182 321 956 125 416 171 774 624 1267 551 908 1051 1117 402 435 537 832 283 912 615 986 248 572 8 614 507 986 104 382 1167 1217 266 537 633 898 11 1124 703 1149 616 836 5 455 772 1040 403 1164 808 810 533 772 551 1103 163 1089 470 1107 1074 1264 49 81 941 1132 316 1261 81 696 31 850 285 1103 838 1251 182 855 953 1122 453 946 107 1039 300 1082 535 1033 378 1210 953 1106 39 1099 219 1180 31 1173 143 209 29 874 318 1125 280 467 78 227 262 391 318 449 641 686 171 561 409 527 187 476 254 649 8 1014 411 669 765 1210 138 455 333 439 158 369 816 1226 334 1036 600 1024 227 1211 778 1136 132 1261 485 848 968 1258 987 1124 194 878 137 302 991 1050 422 1026 255 1116 907 933 256 771 35 701 183 1014 21 614 755 1109 769 827 57 1086 598 1177 1…
Output: 3

Constraints:

1 <= n <= 2857; 0 <= m <= 5714.

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