Marisa and Reimu have lost each other in the Bamboo Forest of the Lost. The forest can be represented as a undirected graph of $n$ vertices and $m$ edges. Marisa is currently at vertex $a$, and Reimu is currently at vertex $b$.
Every $1$ unit of time, Marisa and Reimu move to any adjacent vertex (they will not stand still, as they are in a hurry now). Find the earliest time when they will meet each other again.
### Input
- The first line contains 2 integers $n, m$.
- The second line contains 2 integers $a, b$.
- The next $m$ lines, each line contains 2 integers $u, v$, there is an edge between $u$ and $v$.
### Output
- Print the earliest time when they will meet each other again. Or print `-1` if they get lost forever...
### Constraints
- $1 \le n, m \le 10^5$.
- $1 \le u, v,a, b \le n$.
### Example
Input:
```
6 6
1 6
1 2
2 3
3 4
2 4
6 5
5 4
```
Output:
```
2
```
#### **Note**: Marisa and Reimu will meet each other at $4$.