마법 왕국

마법 왕국에는 도시들을 양방향으로 잇는 마법 포털 네트워크가 있다. 각 포털은 두 도시를 직접 연결하여 그 사이를 빠르게 오갈 수 있게 해 준다. 하나의 포털로 직접 연결된 두 도시를 서로 이웃한 도시라고 한다.

알버트 왕자와 베티 공주는 서로 이웃한 두 도시에 살고 있으며 깊이 사랑하지만, 한 번도 직접 만난 적이 없고 같은 도시에 동시에 있는 것을 극도로 꺼린다. 그래서 두 사람은 어디를 가든 항상 서로 이웃한, 서로 다른 두 도시(포털로 직접 연결된 서로 다른 두 도시)에 머물러야 한다.

이동할 때 두 사람은 포털을 이용한다. 한 번의 이동에서 다음 중 하나를 할 수 있다.

• 둘 중 한 사람만 포털 하나를 지나 이동한다(다른 한 사람은 그대로 머문다).
• 두 사람이 동시에, 각자 서로 다른 포털을 지나 이동한다.

두 사람은 절대로 같은 포털을 동시에 지날 수 없다. 그리고 매 이동이 끝난 뒤에도 두 사람은 다시 서로 이웃한, 서로 다른 두 도시에 있어야 한다.

한 번의 이동 비용은 움직인 사람 수로 센다. 한 사람만 움직이면 $1$번의 이동이고, 두 사람이 동시에 움직이면 $2$번의 이동이다.

포털 네트워크와 두 사람의 출발 도시, 도착 도시가 주어질 때, 알버트와 베티를 출발한 이웃 도시 쌍에서 목표로 하는 이웃 도시 쌍으로 옮기는 데 필요한 최소 이동 횟수를 구하여라. 항상 가능함이 보장된다.

첫째 줄에 여섯 개의 정수 $n$, $m$, $a_1$, $b_1$, $a_2$, $b_2$가 주어진다. 여기서 $n$ ($3 \le n \le 100$)은 도시의 수이고(도시는 $1$번부터 $n$번까지 번호가 매겨진다), $m$ ($2 \le m \le 1000$)은 포털의 수이다. 알버트와 베티는 각각 서로 이웃한 도시 $a_1$, $b_1$ ($1 \le a_1, b_1 \le n$, $a_1 \ne b_1$)에서 출발하여 서로 이웃한 도시 $a_2$, $b_2$ ($1 \le a_2, b_2 \le n$, $a_2 \ne b_2$)로 가려고 한다. 단 $a_1 \ne a_2$ 또는 $b_1 \ne b_2$이다.

이어지는 $m$개의 줄에는 각 포털이 연결하는 두 도시 $p_{i1}$, $p_{i2}$ ($1 \le p_{i1}, p_{i2} \le n$, $p_{i1} \ne p_{i2}$)가 주어진다. 어떤 두 도시를 연결하는 포털은 많아야 하나이다.

알버트와 베티를 $(a_1, b_1)$에서 $(a_2, b_2)$로 옮기는 데 필요한 최소 이동 횟수를 정수 하나로 출력한다.