CT43394

Vani's bridges Fewest Hops

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Caravans arrive at the indigo vats of Bluehollow with crates of bridges, and Vani the factor must account for every last one. 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 <= 1582; 0 <= m <= 3164.

Example 1:

Input: 1530 3135 1 1530 648 674 153 574 26 833 590 1449 287 713 181 593 597 1016 892 1103 387 514 1002 1024 280 1302 1112 1518 386 569 883 1196 334 667 994 1306 186 1065 644 938 25 509 865 1491 407 1407 148 273 338 1199 784 1518 55 1502 387 1081 27 567 913 1344 1061 1528 66 293 83 1165 44 156 543 858 386 546 131 527 12 282 58 837 281 1378 578 1163 114 893 1317 1369 77 271 1331 1463 735 969 58 1503 49 1371 23 997 50 265 2 1332 172 457 778 1354 743 819 1199 1394 864 907 104 339 122 1228 386 849 531 1524 880 1212 487 629 823 1528 476 913 403 987 549 605 432 1234 122 1051 40 215 900 1411 673 1257 1031 1282 501 1459 751 1484 1 632 565 832 399 778 180 579 1226 1459 989 1027 1074 1277 126 1112 1046 1096 413 1326 1062 1068 354 580 249 844 1026 1505 1089 1103 1068 1426 368 1011 1309 1444 355 491 593 710 1…
Output: 6

Example 2:

Input: 155 204 1 155 11 81 46 111 82 83 68 113 150 155 32 101 1 137 11 16 35 40 36 144 31 63 40 123 24 127 19 123 21 22 98 148 37 103 111 138 13 145 82 93 133 135 18 111 77 128 93 116 32 70 53 62 1 120 92 128 68 82 23 132 44 106 109 123 112 131 79 135 51 61 92 113 18 78 1 57 72 124 57 74 54 141 107 144 1 70 56 79 34 59 63 95 40 137 31 129 9 53 63 94 30 116 39 117 46 85 70 93 42 115 1 83 19 91 7 127 3 51 33 91 1 114 36 42 46 80 83 154 71 99 13 144 50 82 46 116 112 148 4 28 46 134 85 97 87 88 57 121 24 121 110 155 57 140 35 149 88 96 45 63 84 92 23 137 143 147 72 111 77 126 6 116 11 38 52 131 104 119 29 38 4 32 40 79 37 110 94 112 47 52 1 146 25 49 31 46 101 126 55 72 8 105 96 101 72 100 118 124 65 99 3 79 66 102 48 131 4 19 21 45 19 127 59 108 77 105 20 151 89 142 12 126 2 129 92 126 56 82 85 142 …
Output: 2

Example 3:

Input: 287 286 1 287 203 280 279 285 120 214 28 248 11 266 88 219 168 216 14 156 99 121 70 273 99 193 80 234 103 186 28 217 148 278 253 269 98 143 87 190 180 274 179 191 135 270 149 221 42 172 123 270 41 167 17 261 94 140 52 274 164 181 45 109 52 70 10 180 112 241 43 202 102 197 59 281 76 84 76 247 169 240 52 201 6 234 24 177 127 230 114 219 41 61 199 267 37 237 78 224 189 234 78 278 49 157 166 274 81 106 36 188 5 69 4 231 66 274 24 187 26 160 150 183 193 263 128 219 125 238 66 260 11 121 108 182 189 255 45 72 41 143 124 207 126 230 71 135 202 283 105 150 80 220 40 226 46 151 31 235 1 80 168 269 115 141 192 285 152 223 250 265 82 269 171 261 215 265 117 239 5 55 41 257 216 222 46 96 78 208 86 125 52 57 145 253 190 274 77 124 50 217 118 237 204 252 108 259 49 76 141 236 197 223 116 128 13 273 172 …
Output: 5

Constraints:

1 <= n <= 1582; 0 <= m <= 3164.

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