CT39607

Pavel's Roving roads

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Every season at the gull cliffs of Screech Point, someone must rank apprentices for the new term. This year the task falls to Pavel, armed only with the roads register. 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 <= 1224; 0 <= m <= 2448.

Example 1:

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

Example 2:

Input: 345 554 1 345 7 139 20 27 54 79 221 314 70 299 164 255 50 217 51 154 157 220 27 335 44 234 131 338 138 317 32 295 32 80 4 246 51 168 67 233 157 277 112 190 89 317 150 318 20 261 29 35 62 130 8 136 121 263 46 122 51 340 191 280 68 314 63 176 10 332 160 262 30 256 197 314 292 307 25 34 103 317 66 160 108 192 12 274 97 345 163 291 102 305 15 229 227 309 106 278 53 123 20 188 126 133 104 303 68 330 156 166 96 156 125 327 167 198 189 278 50 52 11 14 180 268 164 216 35 43 74 178 69 272 176 210 2 88 150 182 78 91 13 218 14 157 156 252 82 310 153 307 67 315 61 106 196 327 261 324 73 262 134 157 304 322 204 263 82 116 149 276 332 342 89 161 333 345 217 337 48 124 78 251 76 299 43 99 25 314 45 317 306 317 176 256 39 82 257 340 34 286 1 260 46 102 2 61 38 65 155 322 13 41 14 340 110 295 153 278 191 2…
Output: 5

Example 3:

Input: 170 1386 1 170 14 122 11 53 61 165 1 117 125 126 33 115 45 140 72 124 42 57 10 99 58 103 15 159 40 68 70 140 65 97 31 132 86 110 96 100 33 112 3 8 24 61 14 16 36 119 72 103 126 147 32 135 42 73 106 154 86 160 74 124 116 128 84 108 112 167 67 94 4 156 125 148 4 129 111 130 62 132 27 32 10 135 133 158 94 104 38 91 115 145 17 38 144 145 99 163 77 167 14 20 78 82 35 80 71 109 72 93 21 39 132 142 79 121 22 155 19 77 16 157 29 50 126 165 85 93 33 61 103 143 131 135 63 74 8 148 13 25 8 70 19 64 28 97 16 152 29 150 33 75 35 86 142 153 38 157 5 25 107 158 68 103 31 158 17 29 56 158 34 148 3 136 102 156 41 93 46 88 10 62 139 140 58 70 17 20 16 114 68 163 136 159 55 88 49 91 58 110 10 131 126 167 43 46 13 170 134 151 118 158 30 56 2 21 6 116 23 40 160 168 83 107 2 163 74 143 5 144 19 120 23 116 65 10…
Output: 3

Constraints:

1 <= n <= 1224; 0 <= m <= 2448.

Loading...
Test Cases:No test cases
No test cases available.
Pavel's Roving roads - MEDIUM Coding Problem | CodeTikki