CT34343

Manav and the Woven routes

MediumL4 · Loop LordAcceptance: 0.0%XP: 35

Manav found an old ledger of routes in the shed attic at the lantern reef of Glowtide. 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 <= 1558; 0 <= m <= 3116.

Example 1:

Input: 243 348 1 243 171 229 93 229 45 232 79 126 176 191 4 115 71 197 84 95 154 232 15 50 60 230 159 209 80 86 87 174 101 157 192 212 65 227 216 220 136 152 137 168 183 203 151 202 24 136 133 198 48 212 98 188 175 238 178 226 71 236 124 166 46 153 26 219 164 169 32 168 82 136 65 135 52 185 16 73 154 173 19 167 76 226 50 98 124 158 98 180 146 240 79 87 227 231 218 220 174 188 24 204 48 202 101 154 211 216 91 136 17 120 11 83 72 135 8 119 18 164 134 166 77 125 61 111 14 217 162 221 97 220 13 242 60 160 35 110 53 215 57 218 60 79 130 176 50 54 64 78 50 125 35 128 62 151 123 135 162 226 153 232 23 228 10 76 102 153 79 98 51 210 5 9 22 24 189 226 135 213 43 195 156 196 122 158 72 189 98 145 15 194 15 235 76 85 68 239 34 195 65 204 184 230 100 138 30 46 125 222 20 102 141 218 57 65 148 216 106 144 45 …
Output: 7

Example 2:

Input: 421 2000 1 421 25 141 74 391 15 333 213 405 27 142 260 363 20 60 229 316 90 418 287 350 257 362 56 260 94 273 43 375 251 319 249 421 160 411 1 370 215 322 116 276 148 292 342 421 164 311 183 213 18 68 228 266 77 235 65 229 406 418 255 279 253 274 91 175 76 386 35 151 49 296 131 270 258 364 179 398 256 366 299 392 312 369 126 324 139 272 303 393 136 244 187 317 115 244 56 244 347 409 4 366 59 343 195 213 132 360 161 335 20 97 148 170 37 377 93 104 315 339 167 310 145 243 73 107 198 309 48 50 144 344 357 384 252 327 224 238 140 223 112 232 202 294 222 403 356 418 295 401 138 384 127 217 96 115 4 261 76 351 267 316 296 347 166 401 48 104 149 166 46 407 83 299 254 330 233 268 144 322 160 222 72 386 147 297 194 356 50 57 76 130 70 306 173 218 3 86 142 302 285 348 187 261 205 206 348 380 80 252 …
Output: 4

Example 3:

Input: 151 1421 1 151 43 117 25 138 60 142 21 57 72 128 11 73 49 105 101 107 9 125 72 75 88 144 5 119 121 144 88 109 112 135 26 118 69 145 91 114 10 91 54 56 22 65 2 138 64 128 9 14 71 139 105 113 73 98 15 106 74 134 78 125 77 129 39 115 8 26 67 142 93 118 30 133 103 144 62 82 111 127 34 96 45 132 28 39 31 89 108 111 7 73 37 52 92 149 82 114 115 135 44 108 49 68 50 98 14 80 64 112 1 52 76 90 48 139 47 80 3 22 3 5 47 99 28 138 38 109 79 125 38 121 24 57 58 110 16 20 66 120 11 148 6 51 120 135 24 30 45 88 64 141 97 122 70 128 61 105 7 65 64 87 64 110 95 103 106 151 24 26 43 69 96 122 14 47 23 112 7 49 59 94 85 105 119 124 102 109 39 104 68 137 54 76 110 115 92 93 52 53 83 108 80 90 119 134 27 36 3 142 122 139 46 104 4 77 40 93 67 132 44 106 79 89 45 91 9 116 69 115 62 66 50 80 85 117 34 39 82 83 10…
Output: 2

Constraints:

1 <= n <= 1558; 0 <= m <= 3116.

Loading...
Test Cases:No test cases
No test cases available.
Manav and the Woven routes - MEDIUM Coding Problem | CodeTikki