CT33631

Kabir's Ledger of roads

MediumL4 · Loop LordAcceptance: 0.0%XP: 35

Kabir found an old ledger of roads in the stall attic at the indigo vats of Bluehollow. The margin notes pose a precise question. 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 <= 847; 0 <= m <= 1694.

Example 1:

Input: 459 719 1 459 41 405 141 183 215 319 302 367 53 401 160 314 441 445 106 148 333 398 31 311 402 448 293 385 22 106 237 455 116 144 57 437 96 302 382 437 104 263 141 440 75 441 103 441 177 329 173 356 81 413 126 426 321 406 52 262 269 294 29 239 167 256 127 384 145 359 72 239 108 239 58 214 122 183 359 407 161 239 225 405 248 347 59 178 167 194 39 333 39 270 134 346 71 157 92 212 198 276 11 141 303 308 152 347 328 419 32 438 2 7 202 307 109 440 28 394 239 400 30 237 93 246 36 225 176 212 91 193 216 333 235 331 109 232 387 411 109 448 70 85 18 194 66 286 397 399 6 202 114 332 37 131 78 172 217 377 103 291 264 444 292 421 256 457 108 309 241 381 335 453 251 407 74 120 130 225 275 339 271 322 133 329 15 104 127 203 296 307 159 359 207 209 21 295 39 213 63 272 163 391 77 164 130 405 252 330 297 …
Output: 5

Example 2:

Input: 214 756 1 214 34 130 115 141 151 166 85 169 48 66 99 169 43 101 151 199 67 205 76 153 16 36 160 193 72 209 80 209 46 97 65 184 76 172 163 183 33 52 61 206 30 150 2 11 151 154 142 143 175 187 16 176 120 129 56 148 10 151 20 97 86 112 92 172 85 112 2 199 31 33 109 170 19 29 14 87 98 125 102 188 37 117 37 150 68 118 81 189 54 86 7 151 3 85 63 155 7 124 64 160 166 187 134 167 34 102 114 142 155 199 4 149 76 125 170 208 62 198 178 187 66 142 73 174 13 55 62 91 82 132 12 190 99 103 1 24 14 38 102 127 98 172 31 213 49 140 115 213 1 142 1 116 25 66 13 163 14 176 157 161 106 150 27 103 122 162 172 174 110 150 87 192 7 106 103 145 69 191 183 201 102 181 99 124 48 185 20 23 134 196 112 152 38 94 48 186 48 106 46 185 110 128 10 29 37 156 91 173 140 167 74 148 9 183 104 131 70 91 89 164 107 143 5 75 37…
Output: 3

Example 3:

Input: 254 1619 1 254 151 198 216 220 10 52 24 71 146 186 134 166 99 217 77 113 155 252 39 113 57 199 19 37 96 110 125 206 76 166 54 88 13 24 87 128 82 125 49 132 118 252 4 144 220 251 97 219 3 126 93 248 87 95 33 157 122 234 208 251 34 113 209 232 168 193 61 119 76 248 178 200 29 188 47 174 215 227 23 55 122 141 29 45 47 146 77 209 122 250 71 105 35 154 8 38 1 245 8 103 126 159 175 206 23 129 28 57 61 63 133 150 89 134 10 101 47 225 47 64 62 198 136 168 140 176 32 122 95 120 100 230 49 152 51 207 179 226 51 229 136 212 105 145 46 245 117 247 5 19 107 222 142 254 26 229 64 186 101 248 76 249 111 250 6 38 170 185 48 158 112 118 35 216 34 160 99 194 169 246 112 243 74 78 179 190 29 85 12 88 75 235 128 186 134 227 90 127 23 91 57 147 94 251 196 238 32 225 56 95 42 199 27 99 161 245 2 218 150 197 27 …
Output: 2

Constraints:

1 <= n <= 847; 0 <= m <= 1694.

Loading...
Test Cases:No test cases
No test cases available.
Kabir's Ledger of roads - MEDIUM Coding Problem | CodeTikki