CT40701

Fiora's Whispering canals

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Fiora runs the chandlery at the shale slopes of Greystone. Today the books show a list of canals, and the numbers must be worked out before sundown. 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 <= 1135; 0 <= m <= 2270.

Example 1:

Input: 1108 1322 1 1108 105 1080 60 977 437 733 117 353 161 786 311 526 230 502 190 233 311 721 596 902 302 1105 77 1079 377 881 203 1088 1047 1103 697 854 390 688 417 653 525 554 331 335 533 1025 738 962 457 985 930 1083 638 974 354 561 648 664 229 286 375 445 374 568 580 713 413 1056 327 816 146 883 705 1056 20 1082 263 765 462 656 465 895 253 499 324 1085 28 914 542 1023 354 776 711 794 51 238 268 861 22 1052 376 602 445 1056 182 1000 404 1010 703 826 858 879 29 855 524 1073 987 1026 577 685 157 164 100 816 170 991 545 838 957 997 51 465 601 861 99 101 254 756 148 295 302 482 764 886 341 475 569 629 65 603 708 1042 320 466 97 1108 170 940 830 950 619 1108 587 1104 674 732 510 774 820 823 371 1085 410 704 397 509 730 1048 94 939 48 1066 883 1070 165 316 4 320 206 1076 356 959 707 793 129 633 93…
Output: 8

Example 2:

Input: 55 612 1 55 28 30 25 45 18 21 13 40 7 12 11 46 44 52 22 38 14 44 9 32 7 30 13 45 24 49 38 46 7 14 34 43 14 26 50 54 12 46 1 31 13 33 19 39 2 8 11 21 6 25 26 27 7 47 13 50 11 19 21 54 2 22 17 28 12 17 1 14 10 11 12 20 20 29 10 38 23 26 3 53 1 11 11 27 24 35 8 44 45 55 7 17 11 43 12 16 7 25 23 42 22 35 13 27 36 47 34 40 37 54 1 48 37 44 25 37 2 32 10 35 11 49 43 47 28 36 22 49 5 42 26 48 16 18 33 38 35 48 13 34 1 15 3 6 21 46 1 22 48 53 3 35 2 31 24 26 7 20 12 27 9 45 13 53 31 41 27 51 33 50 41 44 35 51 20 39 21 25 46 49 7 37 3 33 32 39 1 24 3 22 21 50 3 54 14 28 15 29 1 45 12 45 1 6 14 46 37 52 3 31 3 46 4 38 7 33 16 52 5 13 8 20 26 42 2 6 15 36 10 29 8 49 33 46 50 53 28 52 31 52 28 29 13 25 36 39 13 49 23 51 12 50 3 18 14 50 24 44 44 49 32 52 16 19 8 12 8 16 27 53 37 53 5 22 27 35 7 55 17 …
Output: 1

Example 3:

Input: 231 1683 1 231 113 201 10 179 75 141 41 171 30 114 104 175 69 79 127 169 117 185 5 88 60 201 199 200 178 225 66 190 20 37 48 75 11 201 96 214 66 172 89 205 147 153 94 226 101 212 57 105 182 206 32 167 131 204 120 199 54 219 140 179 11 34 170 180 4 133 5 190 143 185 19 206 163 190 73 190 198 214 121 184 27 218 94 103 186 214 9 178 22 121 109 163 13 126 105 199 43 129 149 230 17 175 129 223 88 191 103 157 88 161 69 218 3 198 173 202 79 106 77 185 125 170 79 144 32 165 62 106 103 197 49 125 27 194 195 202 68 123 118 127 30 59 33 137 87 193 172 221 136 210 31 89 140 224 130 213 111 178 36 109 42 132 16 162 137 217 47 109 36 172 111 174 36 52 148 226 120 121 32 163 53 141 80 227 144 227 162 210 51 103 37 85 26 79 9 148 71 137 29 206 107 120 99 185 192 199 63 199 192 223 47 90 75 226 39 51 168 2…
Output: 3

Constraints:

1 <= n <= 1135; 0 <= m <= 2270.

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