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>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef pair<ll, P> P3;
typedef pair<P ,P> PP;
constexpr ll MOD = ll(1e9) + 7;
constexpr int IINF = INT_MAX;
constexpr ll LLINF = LLONG_MAX;

vector<bool> IsPrime;
vector<int> primes;

void sieve(int max) {
    IsPrime.resize(max + 1, true);
    IsPrime[0] = IsPrime[1] = false;
    for (int i = 2; i * i <= max; ++i){
        if (IsPrime[i]){
            for (int j = i * i; j <= max; j += i) IsPrime[j] = false;
        }
    }
    for(int i = 0; i <= max; ++i)if(IsPrime[i])primes.push_back(i);
}

int n, m, s, t;
vector<vector<int> > g;
vector<int> dmin[2];

int bfs(){
    for(int i=0;i<2;i++) dmin[i].resize(n,IINF);
    dmin[0][s] = 0;
    queue<P> que;
    que.push({0,s});
    while(!que.empty()){
        P p = que.front();
        que.pop();
        int b = p.first, cur = p.second;
        for(auto nxt : g[cur]){
            if(dmin[b^1][nxt] > dmin[b][cur]+1){
                dmin[b^1][nxt] = dmin[b][cur] + 1;
                que.push({b^1, nxt});
            }
        }
    }
    
    int res = IINF;
    if(dmin[0][t]==2) res = 2;
    else if (dmin[1][t] < IINF) res = *lower_bound(primes.begin(), primes.end(), max(3,dmin[1][t]));
    return res;
}

int main() {
    sieve(1e6);
    cin >> n >> m >> s >> t;
    s--; t--;
    g.resize(n);
    for(int i=0;i<m;i++){
        int u, v;
        cin >> u >> v;
        u--; v--;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    int ans = bfs();
    cout << (ans < IINF ? ans : -1) << endl;
    return 0;
}