CT46618

Chetan and the Fewest Hops

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

The council of the fen lights of Will-o-Wisp pays by the answer, and Chetan intends to earn it. First: the full register of corridors. 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 <= 1994; 0 <= m <= 3988.

Example 1:

Input: 107 861 1 107 59 107 1 5 34 86 62 94 54 65 88 91 20 90 42 51 22 48 43 106 69 70 19 104 65 68 62 97 19 26 38 62 67 90 74 94 46 51 86 104 21 42 22 95 13 107 16 58 34 106 79 91 67 88 61 85 52 64 8 94 31 69 67 73 17 59 55 80 40 96 71 86 2 27 4 21 18 59 89 106 28 67 20 37 67 81 3 62 35 40 40 68 12 104 25 98 56 82 10 65 6 46 6 101 90 105 5 88 69 100 22 75 25 86 34 57 45 98 1 11 87 102 33 36 69 89 45 59 3 16 11 25 26 81 3 42 56 100 24 47 28 89 58 96 23 59 42 71 79 96 34 59 53 104 62 70 7 66 4 88 22 82 21 85 11 53 28 95 21 41 48 95 19 55 7 28 68 90 49 56 12 37 68 78 13 52 25 70 33 34 38 106 28 68 6 61 49 103 2 49 76 88 75 99 49 99 1 13 25 35 60 93 15 63 26 85 60 106 17 97 56 107 43 65 67 102 7 20 62 105 78 92 19 93 16 52 15 76 16 76 12 36 46 101 51 62 26 41 3 32 23 60 52 69 14 68 30 66 43 87 90 10…
Output: 2

Example 2:

Input: 374 2494 1 374 57 271 26 355 32 217 66 176 172 356 254 319 209 344 163 288 98 280 33 88 172 350 54 146 7 201 24 339 47 95 220 345 198 313 146 265 112 309 219 334 140 345 143 149 141 367 164 297 285 341 319 360 2 192 120 188 56 164 114 257 105 166 86 289 11 164 277 289 81 374 209 227 23 229 60 339 10 351 212 260 263 291 65 142 41 300 103 291 95 129 44 180 61 172 89 354 223 260 122 319 23 64 93 236 134 260 137 357 7 165 273 364 156 347 307 342 156 372 277 354 139 326 30 288 244 321 231 329 217 256 138 164 80 126 325 343 252 314 7 96 223 348 102 146 8 102 57 79 61 334 153 209 350 365 200 236 222 233 126 127 234 278 150 229 62 265 167 325 218 224 185 240 184 373 62 131 9 236 174 301 43 91 30 286 243 355 184 342 361 366 102 211 139 146 161 289 126 153 27 57 211 315 32 205 92 334 154 370 43 237 …
Output: 3

Example 3:

Input: 343 2939 1 343 271 279 169 181 167 173 50 295 29 182 141 283 106 117 74 159 92 321 240 272 171 278 148 314 120 265 77 208 68 302 121 337 29 140 110 331 141 161 277 281 8 232 54 287 32 281 140 161 142 265 249 313 111 337 280 324 335 340 14 290 29 195 80 258 1 110 31 73 135 147 66 206 56 200 137 323 49 273 16 156 194 234 132 276 48 68 11 118 11 198 294 328 74 148 11 102 207 309 23 343 41 332 9 150 41 176 170 210 26 86 225 250 32 268 78 230 3 266 17 91 151 160 244 297 215 291 28 284 95 162 248 343 135 230 142 210 221 223 105 175 123 208 60 228 17 177 141 149 65 196 10 280 72 261 224 297 18 75 99 233 17 180 208 284 40 46 45 275 208 307 82 131 31 284 125 294 23 163 101 198 9 11 250 306 223 224 122 263 211 214 258 342 259 307 6 68 266 286 149 230 119 314 191 216 11 234 134 302 87 217 50 313 209 …
Output: 2

Constraints:

1 <= n <= 1994; 0 <= m <= 3988.

Loading...
Test Cases:No test cases
No test cases available.
Chetan and the Fewest Hops - MEDIUM Coding Problem | CodeTikki