프라임 라우팅

Fox Jiro는 ACM-ICPC 2018 아시아 요코하마 지역 대회의 스태프 중 한 명으로, 대회장의 네트워크를 설계하는 일을 맡고 있다. 그의 네트워크는 $N$개의 컴퓨터로 이루어져 있고, 이들은 $M$개의 케이블로 연결되어 있다. $i$번째 케이블은 $a_i$번째 컴퓨터와 $b_i$번째 컴퓨터를 연결하며, 양방향으로 데이터를 전송한다. 여러분의 팀은 대회에서 $S$번째 컴퓨터를 사용하고, 심사 서버는 $T$번째 컴퓨터이다.

그는 소수의 마법 같은 힘으로 참가자들의 성능을 최대화하기 위해 네트워크의 라우팅 알고리즘을 조정하기로 했다. 이 알고리즘에서 패킷(네트워크가 나르는 데이터의 단위)은 가능하다면 소수 번 케이블을 통과하여 여러분의 컴퓨터에서 심사 서버로 보내진다. 불가능하다면 참가자들은 소수의 마법 같은 힘으로 이득을 얻을 수 없다. 이 목표를 달성하기 위해 패킷은 같은 케이블을 여러 번 통과할 수 있다.

여러분은 $S$에서 $T$로 가는 패킷이 케이블을 통과해야 하는 최소 횟수를 계산하는 프로그램을 작성하기로 했다. 패킷이 케이블을 통과하는 횟수가 소수가 될 수 없다면 $-1$을 출력한다.

입력은 하나의 테스트 케이스로 이루어져 있으며, 형식은 다음과 같다.

$N$ $M$ $S$ $T$ $a_1$ $b_1$ $\vdots$ $a_M$ $b_M$

첫째 줄은 네 개의 정수 $N$, $M$, $S$, $T$로 이루어져 있다($2 \leq N \leq 10^5$, $1 \leq M \leq 10^5$, $1 \leq S, T \leq N$, $S \neq T$). 다음 $M$개 줄의 $i$번째 줄은 두 개의 정수 $a_i$와 $b_i$로 이루어져 있으며($1 \leq a_i < b_i \leq N$), 이는 $i$번째 케이블이 네트워크에서 $a_i$번째 컴퓨터와 $b_i$번째 컴퓨터를 연결한다는 뜻이다. 네트워크는 다음 조건을 만족한다고 가정할 수 있다.

• 네트워크에 다중 간선이 없다. 즉, 모든 $i$, $j$($1 \leq i < j \leq M$)에 대해 $(a_i, b_i) \neq (a_j, b_j)$이다.
• $N$개의 컴퓨터에서 보낸 패킷은 몇 개의 케이블을 통과하여 $T$에 도달할 수 있다. 그 개수가 소수일 필요는 없다.

$S$에서 $T$로 보낸 패킷이 케이블을 통과하는 횟수가 소수가 되는 방법이 있다면, 그 최소 소수를 한 줄에 출력한다. 그렇지 않다면 $-1$을 출력한다.