CT29053

Yara's corridors Reckoning

MediumL4 · Loop LordAcceptance: 0.0%XP: 35

Legend says the vault under the mining town of Ironvein opens only for a perfect tally of corridors. Yara means to find out. 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 <= 522; 0 <= m <= 1044.

Example 1:

Input: 298 467 1 298 122 161 29 83 80 160 26 278 146 260 185 195 106 203 118 179 78 185 98 137 199 260 15 83 47 84 23 135 38 255 67 196 4 298 91 239 19 250 86 102 78 197 7 253 37 42 47 241 50 240 26 78 32 255 93 277 83 90 52 271 34 130 5 225 51 206 59 283 86 224 101 270 78 274 13 126 66 103 11 95 18 118 264 275 170 219 49 243 144 183 2 207 69 177 60 142 90 119 12 138 167 246 210 270 106 225 3 267 106 151 38 87 224 283 127 222 93 118 159 260 34 212 168 273 140 215 96 205 152 243 116 174 57 265 252 285 71 273 82 246 119 271 3 283 161 222 192 195 76 216 48 176 204 292 116 135 144 269 120 133 41 131 102 185 90 184 109 291 239 261 66 149 189 272 20 101 9 117 73 252 160 195 265 282 17 287 104 195 61 107 186 228 76 113 20 273 207 296 6 232 71 141 28 220 52 292 197 282 128 289 94 236 212 275 5 256 16 253 26 126 128 255 65 268 21 212 75 211 166 196 129 204 69 294 124 218 6 62 14 146 63 77 170 267 152 286 5 92 75 225 128 245 13 200 125 158 167 256 96 159 150 209 27 240 102 113 286 288 148 243 43 280 62 228 239 298 110 242 118 131 7 25 261 266 16 277 19 89 169 233 3 219 73 245 72 225 128 284 59 90 122 266 234 294 18 119 24 203 11 150 56 216 3 39 26 95 62 63 260 270 36 74 75 83 9 204 91 132 27 192 116 278 187 257 18 87 33 224 15 123 22 248 8 155 56 181 53 216 53 111 23 293 13 46 74 94 28 39 17 79 14 176 52 98 207 233 34 159 44 109 146 275 67 185 50 152 195 271 40 84 89 249 52 170 197 234 138 213 78 173 46 166 69 118 195 229 99 118 10 19 5 115 210 276 34 208 85 258 209 293 132 198 46 294 48 290 103 271 49 275 30 45 32 67 68 268 57 260 137 215 122 183 118 226 203 292 96 278 86 129 50 135 190 247 8 131 119 164 78 111 121 190 48 200 27 131 28 225 153 283 40 193 144 290 106 198 54 149 56 201 125 257 174 290 156 198 88 120 14 73 158 235 40 182 70 144 23 118 205 279 78 87 219 287 32 263 53 163 142 293 147 163 36 152 11 171 150 211 112 221 134 291 52 284 142 155 22 146 40 179 141 270 77 152 142 222 20 258 93 175 24 45 129 245 65 153 133 295 168 257 202 239 71 240 162 240 291 298 125 207 7 203 98 135 13 222 38 111 25 69 39 152 285 293 22 216 56 165 165 268 22 240 6 291 78 248 179 218 24 186 9 156 117 161 143 268 101 108 3 160 201 251 105 270 204 234 153 297 241 244 7 84 61 192 3 136 78 161 34 43 18 188 84 147 15 76 125 171 2 62 107 219 30 251 146 293 34 136 16 72 145 231 178 296 111 231 35 75 10 78 174 220 65 125 34 275 36 146 84 214 108 219 213 235 263 270 42 175 138 222 47 222 178 200 22 169 153 202 145 149 105 113 176 237 191 276 7 256 129 285 197 238 190 257 177 281 140 281 123 208 20 46 81 260 163 289 16 112 200 271 123 153 223 239 4 284 146 203 25 61 104 163 185 284 97 109 66 288 2 95 8 197 107 292 3 278 60 289 23 294 60 134 96 231 55 68 240 246 51 209 3 196 61 226 22 165 99 279 29 88 1 86 78 262 127 230 82 126 29 60 44 222 55 138 9 288 210 268 217 271 93 208 139 298 1 10 100 148 222 294 30 259 158 287 21 86 106 274 42 106 180 235 26 170 88 143 101 116 58 85 146 287 18 219 69 115 119 256 10 97 227 281 23 155 178 186 172 180 31 220 154 280 66 118 122 267 6 66 121 253 104 242 40 235 33 65 180 254 21 184 81 172 68 248 189 277 121 293 51 194 114 159 180 253 58 70 167 191 116 236 57 251 260 295 185 239 84 269 33 167 248 293 14 255 203 273 3 64 236 260 163 168 79 145 140 271 69 127 149 152 19 114 32 215 16 270 132 187 112 154 211 276 82 140 53 136 247 290 32 219 126 171 191 202 157 209 161 266 3 205 13 244 15 100 125 226 27 255 40 218 120 174 134 275
Output: 5

Example 2:

Input: 286 672 1 286 160 245 11 204 248 259 50 218 156 214 111 219 103 179 51 252 82 113 9 26 16 233 16 212 139 160 102 111 137 255 33 67 61 171 123 250 88 186 180 233 140 158 170 228 171 275 18 43 19 73 132 165 9 195 45 103 91 155 64 67 33 148 64 161 129 134 37 165 4 63 64 188 8 154 4 222 80 94 72 245 105 261 206 251 115 286 3 36 197 230 184 286 39 262 141 207 83 156 133 250 151 204 133 199 118 280 147 275 55 76 221 228 97 189 62 179 228 249 8 135 75 164 24 66 25 248 138 164 250 265 64 192 121 203 209 223 58 69 168 174 1 124 30 285 4 11 6 95 245 249 41 252 63 161 237 256 128 198 109 263 5 188 58 188 30 73 19 131 69 286 175 257 201 261 177 248 150 154 202 211 6 208 5 226 67 130 14 214 94 113 27 129 31 191 112 241 70 194 93 226 86 197 168 221 149 212 81 129 275 280 106 167 5 169 175 226 176 193 170 217 54 261 20 170 6 219 16 279 102 190 141 224 16 80 20 79 144 266 51 104 3 79 6 134 149 271 22 78 66 217 28 176 52 251 132 212 81 114 119 226 233 274 34 268 227 244 3 166 122 194 144 176 138 218 12 131 10 182 196 237 18 191 21 42 131 271 28 245 65 252 119 133 30 155 176 224 39 82 82 275 72 104 6 273 42 260 35 248 1 234 198 202 170 210 21 276 155 272 26 230 139 143 167 275 1 26 117 184 141 199 134 198 187 278 128 201 13 68 47 286 67 236 40 272 246 266 232 266 108 124 73 248 4 162 39 250 162 271 102 140 237 257 121 148 144 156 43 91 25 58 105 130 175 194 135 160 6 199 149 203 66 223 59 222 92 236 238 254 41 122 152 278 47 162 21 87 144 284 232 281 31 281 137 199 150 251 129 179 174 233 20 153 51 243 252 262 72 73 89 140 94 128 146 155 4 198 4 178 9 159 25 285 237 261 59 171 47 263 38 51 67 277 19 225 131 148 106 120 154 260 83 237 55 63 218 253 132 231 140 221 57 171 86 157 71 152 46 71 34 75 141 229 65 128 195 252 113 177 239 274 95 165 82 203 155 266 48 160 74 111 182 276 113 169 10 176 71 207 221 283 148 263 111 189 172 195 225 252 71 140 166 267 48 254 188 225 177 201 53 58 39 159 240 264 17 30 79 194 160 195 157 236 229 264 55 283 55 82 73 192 1 271 59 91 120 266 2 159 112 255 76 99 201 244 275 285 54 129 14 207 27 210 117 154 188 259 177 281 133 256 150 240 11 128 16 282 24 28 138 143 52 229 134 188 20 133 192 276 11 121 129 228 160 225 165 245 103 262 5 128 43 78 20 254 145 177 162 229 165 227 20 117 48 146 96 111 189 234 92 145 45 277 18 134 192 283 15 53 52 145 22 281 44 108 100 237 66 269 126 157 37 64 155 218 82 244 180 247 57 215 100 112 17 54 148 218 16 190 26 157 56 278 149 253 29 92 19 185 155 158 45 92 91 209 7 204 75 106 42 241 111 163 159 263 118 223 225 242 6 267 239 278 135 197 101 274 175 201 96 263 36 238 105 267 169 209 144 164 154 194 184 235 122 275 122 235 257 283 3 163 57 258 20 50 38 108 126 217 45 285 90 181 246 251 119 212 1 205 1 30 150 239 48 187 18 224 21 67 2 8 9 20 71 118 166 253 81 238 10 283 99 256 125 233 249 272 88 210 201 271 98 184 63 219 127 158 28 39 71 224 60 175 5 151 85 209 125 187 213 275 23 203 259 277 114 186 46 172 150 214 38 74 64 65 62 137 40 116 53 72 31 66 80 224 10 183 28 171 87 221 51 264 77 171 169 225 6 161 105 134 270 283 82 142 16 231 168 181 70 175 29 269 32 83 19 82 138 151 74 286 243 278 171 255 78 101 113 256 159 244 77 90 229 277 10 131 120 245 133 163 214 282 6 204 57 157 256 277 156 250 134 246 12 233 85 185 93 211 210 221 233 260 108 182 50 262 185 276 127 217 12 108 69 157 61 241 99 283 91 97 149 153 78 215 52 241 200 206 213 245 126 136 60 279 187 286 110 258 91 221 18 226 82 134 17 68 9 157 5 276 4 227 13 186 22 168 49 108 130 272 114 135 151 272 78 93 154 159 109 256 29 35 134 186 7 260 160 180 60 220 154 182 128 173 1 153 33 125 202 217 159 202 110 178 32 117 23 65 175 216 184 191 108 263 74 117 43 197 88 225 73 226 200 248 86 237 242 284 74 212 90 183 201 256 103 187 136 139 140 143 135 224 222 270 192 250 217 262 156 232 38 68 24 114 21 76 122 283 55 173 203 226 5 58 122 259 40 134 95 178 13 172 17 87 89 246 106 148 104 256 55 115 162 242 30 198 18 122 36 135 122 129 27 96 133 213 66 207 95 195 148 217 142 184 119 246 1 151 156 200 59 84 30 56 135 145 4 255 7 282 190 219 46 158 189 210 68 134 10 159 172 278 186 217 126 170 194 286 124 201 112 129 140 278 235 284 77 168 226 280 59 224 78 195 53 256 191 227 11 227 24 273 212 244 16 95 148 221 243 263 117 251 5 57 97 130 193 213 222 244 119 146 79 240 213 260 228 270 122 186 61 78 51 56 17 34 153 197 195 269 143 183 109 267 22 25 45 118 11 240 51 219 58 152 125 268 209 224 107 252 64 145 206 278 14 152 45 127 137 142 34 183 199 239 2 197 99 141 37 229 7 96 6 243 66 127 156 213 53 157 14 170 56 79 223 273 100 244 21 125 39 148 211 247 27 254 165 195 149 284 76 187 101 163 148 191 187 240 13 43 41 171 9 215 39 51 16 201 93 275 35 188 63 266 84 239 153 169 235 254 119 282 132 275 25 281 36 115 150 264 83 275 61 175 110 237 196 233 128 213 45 281 5 134 18 275 81 266 120 182 37 129 71 124 3 225 66 247 125 258 5 205 229 253 5 228 44 220 43 93 182 259 108 162 17 243 107 197 73 103 143 165 22 271
Output: 4

Example 3:

Input: 2 1 1 2 1 2
Output: 1

Constraints:

1 <= n <= 522; 0 <= m <= 1044.

Loading...
Test Cases:No test cases
No test cases available.
Yara's corridors Reckoning - MEDIUM Coding Problem | CodeTikki