요원 007

요원 007이 숙적 디레퍼런스드 널포인터 박사(줄여서 널 박사)의 계획을 알아냈다. 널 박사는 서버 두 대 가운데 한 대의 전원 플러그를 뽑으려 한다. 박사는 이미 서버실로 가고 있어서, 007도 함께 아침을 먹던 상대를 언젠가 떠나야 한다.

두 사람은 위성 관측 시스템을 해킹해 두어서 서로의 위치를 늘 안다. 이 시스템은 대상 지역을 연결된 무방향 그래프로 보여 준다. 007, 널 박사, 서버 두 대는 각각 정점 하나에 있다. 서버 두 대는 같은 서버실에 있으므로 인접한 두 정점에 놓여 있다.

시간은 단위 시간으로 나뉜다. 한 단위 시간에는 널 박사가 먼저 행동하고, 그다음 007이 행동한다.

널 박사는 간선 하나를 따라 이동하거나, 제자리에 머무르거나, 서 있는 정점에 서버가 있으면 그 서버의 플러그를 뽑는다.

007은 간선 하나를 따라 이동하거나 제자리에 머무른다. 행동을 마친 뒤 널 박사와 같은 정점에 있으면 널 박사를 잡는다.

플러그를 뽑는 데는 단위 시간 하나가 온전히 걸리지만, 007은 그 일을 중간에 막지 못한다. 널 박사가 플러그를 뽑기 시작하면 박사는 목적을 이룬다. 007이 같은 단위 시간에 그 정점으로 가도 이미 늦다.

007은 널 박사를 잡거나, 널 박사가 영원히 플러그를 뽑지 못하게 하면 성공한다.

007이 $T$단위 시간 동안 아침을 먹는다는 말은, 처음 $T$개의 단위 시간에 007이 행동하지 않는다는 뜻이다. 아침을 먹는 동안 007은 아무도 잡지 못한다. 널 박사가 007과 같은 정점에 와도 마찬가지다.

널 박사가 어떻게 움직이든 007이 반드시 성공하도록, 007이 아침을 먹을 수 있는 최대 단위 시간 수를 구하라.

첫째 줄에 정점 수 $N$과 간선 수 $M$이 주어진다. 정점 번호는 $1$부터 $N$까지다.

둘째 줄에 서로 다른 네 정수 $s$, $d$, $a$, $b$ ($1 \le s, d, a, b \le N$)가 주어진다. 차례대로 007의 처음 위치, 널 박사의 처음 위치, 서버 두 대의 위치다.

다음 $M$개 줄에는 간선 하나를 나타내는 두 정수 $u$와 $v$ ($1 \le u, v \le N$)가 주어진다.

그래프는 연결되어 있고, 정점 $a$와 정점 $b$는 간선으로 이어져 있다.

007이 성공을 보장하면서 아침을 먹을 수 있는 최대 단위 시간 수를 한 줄에 출력한다. 첫 단위 시간에 바로 떠나야 하면 $0$을 출력한다. 007이 무엇을 해도 성공할 수 없으면 $-1$을 출력한다.

$4 \le N \le 200\,000$, $3 \le M \le 600\,000$.