#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define debug(x) cout<<#x<<": "<<x<<endl
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
using ll=long long;
using ull=unsigned long long;
#define int long long
struct node
{
    int u,w,ck;
    bool operator<(const node&t)const{
        return w>t.w;
    }
};
void solve(){
    int n,m,k,d;
    cin>>n>>m>>k>>d;
    vector<vector<int>> adj(n+1);
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    map<pair<int,int>,int> mp;
    queue<int> q;
    vector<bool> vis(n+1);
    q.push(k);
    int cd=0;
    while(!q.empty()){
        int cn=q.size();
        for(int i=0;i<cn;i++){
            int cu=q.front();
            q.pop();
            if(vis[cu])
                continue;
            vis[cu]=1;
            mp[{min(k,cu),max(k,cu)}]=cd;
            // kd[cu]=cd;
            for(auto x:adj[cu]){
                q.push(x);
            }
        }
        cd++;
    }
    for(int i=1;i<=n;i++)
        mp[{i,i}]=0;
    vector<int> res(n+1,1e18);
    vector<int> vvvv(n+1);
    auto dij=[&](){
        priority_queue<node> q;
        q.push({1,0,k});
        res[1]=0;
        while(!q.empty()){
            node cur=q.top();
            q.pop();
            if(vvvv[cur.u])
                continue;
            vvvv[cur.u]=1;            
            for(auto x:adj[cur.u]){
                int dis=mp[{min(x,cur.ck),max(x,cur.ck)}];

                if(d-dis<=0){
                    if(res[cur.u]+d<res[x]){
                        res[x]=res[cur.u]+d;
                        q.push({x,res[cur.u]+d,x});
                    }
                    for(auto xx:adj[x]){
                        mp[{min(xx,x),max(xx,x)}]=1;
                    }
                }
                else{
                    if(res[cur.u]+d-dis<res[x]){
                        res[x]=res[cur.u]+d-dis;
                        q.push({x,res[cur.u]+d-dis,cur.ck});
                    }
                    for(auto xx:adj[x]){
                        if(mp.count({xx,cur.ck})){
                            mp[{min(xx,cur.ck),max(xx,cur.ck)}]=min(mp[{min(xx,cur.ck),max(xx,cur.ck)}],dis+1);
                        }
                        else
                            mp[{min(xx,cur.ck),max(xx,cur.ck)}]=dis+1;

                    }
                }
            }

        }
    };
    dij();
    cout<<res[n]<<endl;
}
signed main(){
    ios::sync_with_stdio(0);
    cout.tie(0);
    cin.tie(0);
    int t=1;
    while(t--){
        solve();
    }
}