2034 Caravans

/*
Author : MadhavCoding
*/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define in(n) int n; cin>>n;
#define inll(n) ll n; cin>>n;
#define in2(x, y) int x, y; cin>>x>>y;
#define inll2(x, y) ll x, y; cin>>x>>y;
#define ins(s) string s; cin>>s;
#define vi vector<int>
#define vll vector<ll>
#define vpi vector<pair<int, int>>
#define vpl vector<pair<ll, ll>>
#define pi pair<int, int>
#define pll pair<ll, ll>
#define ll long long
#define ld long double
#define pb push_back
#define pbb pop_back()
#define endl "\n"
#define N 1e5
#define MOD 1e9+7

// debugging statements
#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x <<" "; _print(x); cerr << endl;
#else
#define debug(x)
#endif

using namespace std;
using namespace __gnu_pbds;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef tree<ll, ll, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_map;

template<class T> void _print(T t) {cerr << t;}
template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.first); cerr << ","; _print(p.second); cerr << "}";}
template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}

void distance1(vector<vector<int>>& graph, vector<int>& vis, vector<int>& dist, int a)
{
    vis[a] = 1;
    queue<int> q;
    q.push(a);
    while(!q.empty())
    {
        int u = q.front(); q.pop();
        for(int i = 0; i < graph[u].size(); i++)
        {
            int v = graph[u][i];
            if(!vis[v])
            {
                vis[v] = 1;
                q.push(v);
                dist[v] = dist[u]+1;
            }
        }
    }
}

int main(int argc, char const *argv[])
{

#ifndef ONLINE_JUDGE
    freopen("error.txt", "w", stderr);
#endif

ios::sync_with_stdio(0);
cin.tie(0);

int t = 1;
while(t--)
{
    in2(v, e);
    vector graph(v, vi());
    for (int i = 0; i < e; i++)
    {
        in2(a,b); a--; b--;
        graph[a].pb(b);
        graph[b].pb(a);
    }
    debug(graph);

    in2(s,f); s--; f--; in(r); r--;

    vi vis(v);

    vi distr(v, INT_MAX); distr[r] = 0;
    distance1(graph, vis, distr, r);
    debug(distr);
    for(int i = 0; i < v; i++) vis[i] = 0;

    vi dists(v, INT_MAX); dists[s] = 0;
    distance1(graph, vis, dists, s);
    debug(dists);
    for(int i = 0; i < v; i++) vis[i] = 0;

    int mini = dists[f]; debug(mini);

    int maxd = 0;
    for(int i = 0; i < v; i++) maxd = max(maxd, distr[i]);
    debug(maxd);

    int low = 0, high = maxd;
    while (low <= high)
    {
        for(int i = 0; i < v; i++) vis[i] = 0;
        int mid = low + (high - low)/2; debug(mid);
        for(int i = 0; i < v; i++)
        {
            if(distr[i] <= mid) vis[i] = 1;
        }
        if(vis[s] == 1) {high = mid - 1; continue;}
        vi dist(v, INT_MAX); dist[s] = 0;
        distance1(graph, vis, dist, s);
        debug(dist);
        if(dist[f] == mini) low = mid + 1;
        else high = mid - 1;
    }

    cout<<low<<endl;

}
return 0;
}