#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <climits>
#include <cstring>
#include <cassert>


using namespace std;
#define SZ(x) (int)(x.size())
#define REP(i, n) for(int i=0;i<n;++i)
#define FOR(i, a, b) for(int i=a;i<b;++i)
#define RREP(i, n) for(int i=n-1;i>=0;--i)
#define RFOR(i, a, b) for(int i=b-1;i>=a;--i)

#define all(x) begin(x),end(x)
#define dump(x) cerr<<#x<<" = "<<(x)<<endl
#define debug(x) cerr<<#x<<" = "<<(x)<<" (L"<<__LINE__<<")"<< endl;

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using P = pair<int, int>;
const double eps = 1e-8;
const ll MOD = 1000000007;
const int INF = INT_MAX / 2;
const ll LINF = LLONG_MAX / 2;

template<class T>
bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
bool chmin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}


template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> p) {
    os << p.first << ":" << p.second;
    return os;
}

template<class T>
ostream &operator<<(ostream &os, const vector<T> &v) {
    os << "[";
    REP(i, SZ(v)) {
        if (i) os << ", ";
        os << v[i];
    }
    return os << "]";
}

// edit

using Int = int;
template<typename T = int,
typename E = int,
typename F = function < T(T, E)> ,
typename Compare = function < bool(T, T) >>
class Dijkstra {
public:
    Int N;
    T s_value;
    T init_value;
    F f;
    Compare cmp;
    
    vector <T> dist;
    vector <vector<pair < int, E>>>
    G; // first : index, second : E
    
    
    Dijkstra(Int N, T init_value = INF, T s_value = 0,
             F f = [](T l, E r) { return l + r; },
             Compare cmp = [](T l, T r) { return l > r; }
             ) : N(N), s_value(s_value), init_value(init_value), f(f), cmp(cmp) {
        dist.resize(N, init_value);
        G.resize(N);
    }
    
    void add_edge(int f, int t, E e) {
        G[f].push_back(make_pair(t, e));
    }
    
    void compute(int s) {
        using P = pair<T, int>;
        auto pq_cmp = [this](P l, P r) -> bool {
            return cmp(l.first, r.first);
        };
        priority_queue<P, vector<P>, decltype(pq_cmp)> que(pq_cmp);
        fill(dist.begin(), dist.end(), init_value);
        dist[s] = s_value;
        
        que.push(P(dist[s], s));
        
        while (!que.empty()) {
            P p = que.top();
            que.pop();
            int v = p.second;
            
            //            if (!cmp(dist[v], p.first) && (dist[v] != p.first)) continue;
            if (cmp(p.first, dist[v])) continue;
            
            for (int i = 0; i < G[v].size(); i++) {
                int to_idx = G[v][i].first;
                E to_e = G[v][i].second;
                
                if (cmp(dist[to_idx], f(dist[v], to_e)) && !(dist[to_idx] == init_value && dist[v] == init_value)) {
                    dist[to_idx] = f(dist[v], to_e);
                    que.push(P(dist[to_idx], to_idx));
                }
            }
        }
    }
    
    T get_dist(int v) {
        return dist[v];
    }
    
};


auto get_primes(){
    int LIM = 1000000;
    
    vector<bool> prime(LIM, true);
    prime[0] = prime[1] = false;
    
    for(int i = 2; i < LIM; ++i){
        if(prime[i]){
            for(int j = i * 2; j < LIM; j += i){
                prime[j] = false;
            }
        }
    }
    
    vector<int> ret;
    
    for(int i = 0; i < LIM; ++i){
        if(prime[i]){
            ret.push_back(i);
        }
    }
    
    return ret;
}

void solve() {
    int N, M, S, T;
    cin >> N >> M >> S >> T;
    S--;
    T--;
    

    vector<set<int>> G(N);
    Dijkstra<> dij(2 * N);
    
    for(int i = 0; i < M; ++i){
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        
        dij.add_edge(a, b + N, 1);
        dij.add_edge(a + N, b, 1);
        dij.add_edge(b, a + N, 1);
        dij.add_edge(b + N, a, 1);
        
        G[a].insert(b);
        G[b].insert(a);
        
    }
    
    // 2-check
    for(Int i = 0; i < N; ++i){
        if(G[i].count(S) && G[i].count(T)){
            cout << 2 << endl;
            return;
        }
    }
    
    
    
    
    auto primes = get_primes();
    dij.compute(S);
    
    int term = T + N;
    int dist = dij.get_dist(term);
    
    
    if(dist == INF){
        cout << -1 << endl;
        return;
    }
    
    
    auto pt = lower_bound(all(primes), dist);
    if(*pt == dist){
        cout << dist << endl;
        return;
    }
//    int ans = *pt;
//    if(*pt == ans)
    int ans = *lower_bound(all(primes), dist + 2);
    cout << ans << endl;
    
    

    
    
    

    
}


int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
//    std::ifstream in("input.txt");
//    std::cin.rdbuf(in.rdbuf());

    solve();


    return 0;
}


Measured memory_bytes: 29896