Kingdom of Magic

The Kingdom of Magic has a network of bidirectional magic portals connecting its cities. Each portal directly connects a pair of cities and lets people travel quickly between them. Two cities joined by a portal are called neighboring.

Prince Albert and Princess Betty live in two neighboring cities and are deeply in love, yet they have never met and refuse to ever be in the same city at the same time. Therefore, wherever they go, they must always stay in a pair of neighboring, distinct cities (two different cities directly connected by a portal).

To move, they use the portals. In a single step they may either:

• move just one of them through one portal (the other stays put), or
• move both of them at the same time, each through a different portal.

They may never move through the same portal at the same time. After every step they must again occupy a pair of neighboring, distinct cities.

The cost of a step is the number of people who move: moving one person costs $1$ move, and moving both at once costs $2$ moves.

Given the portal network together with Albert's and Betty's starting cities and their destination cities, compute the minimal total number of moves needed to bring them from their starting pair of neighboring cities to their target pair of neighboring cities. It is guaranteed that this is possible.

The first line contains six integers $n$, $m$, $a_1$, $b_1$, $a_2$, $b_2$. Here $n$ ($3 \le n \le 100$) is the number of cities (numbered from $1$ to $n$) and $m$ ($2 \le m \le 1000$) is the number of portals. Albert and Betty start in the neighboring cities $a_1$ and $b_1$ ($1 \le a_1, b_1 \le n$, $a_1 \ne b_1$) and want to reach the neighboring cities $a_2$ and $b_2$ ($1 \le a_2, b_2 \le n$, $a_2 \ne b_2$), with $a_1 \ne a_2$ or $b_1 \ne b_2$.

Each of the next $m$ lines contains two integers $p_{i1}$ and $p_{i2}$ ($1 \le p_{i1}, p_{i2} \le n$, $p_{i1} \ne p_{i2}$), the two cities connected by that portal. At most one portal connects any pair of cities.

Print a single integer: the minimal total number of moves needed to bring Albert and Betty from $(a_1, b_1)$ to $(a_2, b_2)$.