Problem: Fox Jiro is one of the staffs of the ACM-ICPC 2018 Asia Yokohama Regional Contest and is responsible for designing the network for the venue of the contest. His network consists of $N$ computers, which are connected by $M$ cables. The $i$-th cable connects the $a_i$-th computer and the $b_i$-th computer, and it carries data in both directions. Your team will use the $S$-th computer in the contest, and a judge server is the $T$-th computer.

He decided to adjust the routing algorithm of the network to maximize the performance of the contestants through the magical power of prime numbers. In this algorithm, a packet (a unit of data carried by the network) is sent from your computer to the judge server passing through the cables a prime number of times if possible. If it is impossible, the contestants cannot benefit by the magical power of prime numbers. To accomplish this target, a packet is allowed to pass through the same cable multiple times.

You decided to write a program to calculate the minimum number of times a packet from $S$ to $T$ needed to pass through the cables. If the number of times a packet passes through the cables cannot be a prime number, print $-1$.



Input

The input consists of a single test case, formatted as follows.


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


The first line consists of four integers $N, M, S,$ and $T$ ($2 \leq N \leq 10^5, 1 \leq M \leq 10^5, 1 \leq S, T \leq N, S \ne T$). The $i$-th line of the following $M$ lines consists of two integers $a_i$ and $b_i$ ($1 \leq a_i < b_i \leq N$), which means the $i$-th cables connects the $a_i$-th computer and the $b_i$-th computer in the network. You can assume that the network satisfies the following conditions.

* The network has no multi-edge, i.e.,$(a_i, b_i) \ne (a_j, b_j)$ for all $i,j$ ($1 \leq i < j \leq M$).
* The packets from $N$ computers are reachable to $T$ by passing through some number of cables. The number is not necessarily a prime.

Output

If there are ways such that the number of times a packet sent from $S$ to $T$ passes through the cables is a prime number, print the minimum prime number of times in one line. Otherwise, print $-1$.

Examples

Input

5 5 1 5
1 2
1 4
2 3
3 4
3 5


Output

3


Input

5 4 1 5
1 2
2 3
3 4
4 5


Output

-1


Input

2 1 1 2
1 2


Output

3


Input

3 3 1 2
1 2
1 3
2 3


Output

2

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define NUM 100005

enum Type{
	GU,
	KI,
};

struct Info{
	Info(int arg_node_index,int arg_sum_dist,Type arg_type){
		node_index = arg_node_index;
		sum_dist = arg_sum_dist;
		type = arg_type;
	}
	bool operator<(const struct Info &arg) const{
		return sum_dist > arg.sum_dist;
	}
	int node_index,sum_dist;
	Type type;
};

int N,M,S,T;
int table[2*NUM],prime_table[NUM];
int min_dist[2][NUM];
vector<int> G[NUM];
Type rev[2] = {KI,GU};


int main(){

	//20万以下の素数を求める
	for(int i = 0; i < 2*NUM; i++){
		table[i] = 1;
	}
	table[0] = 0;
	table[1] = 0;

	for(int i = 2; i < 2*NUM; i++){
		if(table[i] == 0)continue;

		for(int k = 2*i; k < 2*NUM; k += i){
			table[k] = 0;
		}
	}

	int index = 0;
	for(int i = 3; i < 2*NUM; i++){
		if(table[i] == 1){
			prime_table[index++] = i;
		}
	}

	scanf("%d %d %d %d",&N,&M,&S,&T);

	S--;
	T--;

	int from,to;

	for(int loop = 0; loop < M; loop++){

		scanf("%d %d",&from,&to);
		from--;
		to--;

		G[from].push_back(to);
		G[to].push_back(from);
	}

	for(int i = 0; i < N; i++){
		min_dist[GU][i] = BIG_NUM;
		min_dist[KI][i] = BIG_NUM;
	}

	priority_queue<Info> Q;
	min_dist[GU][S] = 0;
	Q.push(Info(S,0,GU));

	int next_node,next_cost;
	Type next_type;

	while(!Q.empty()){

		if(Q.top().sum_dist > min_dist[Q.top().type][Q.top().node_index]){

			Q.pop();
		}else{

			for(int i = 0; i < G[Q.top().node_index].size(); i++){

				next_node = G[Q.top().node_index][i];
				next_cost = Q.top().sum_dist+1;
				next_type = rev[Q.top().type];

				if(min_dist[next_type][next_node] > next_cost){
					min_dist[next_type][next_node] = next_cost;
					Q.push(Info(next_node,next_cost,next_type));
				}
			}

			Q.pop();
		}
	}

	if(min_dist[GU][T] == 2){

		printf("2\n");

	}else{

		if(min_dist[KI][T] == BIG_NUM){

			printf("-1\n");

		}else{

			int left = 0,right = index-1,mid = (left+right)/2;
			int ans;

			while(left <= right){

				if(prime_table[mid] >= min_dist[KI][T]){

					ans = prime_table[mid];
					right = mid-1;

				}else{

					left = mid+1;
				}
				mid = (left+right)/2;
			}

			printf("%d\n",ans);
		}
	}

	return 0;
}