#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
vector<int> nb[N];
ll ds[N],dk[N],dt[N];
int vis[N];
int n,m,k;ll rg;
bool flag[N];

void bfs(int s, ll *dis)
{
    //dis all -1
    queue<int> q;
    q.push(s);dis[s]=0;
    while(!q.empty())
    {
        int u=q.front();q.pop();
        for(auto v:nb[u])
        {
            if(dis[v] != -1)
                continue;
            dis[v] = dis[u] + 1;
            q.push(v);
        }
    }
}


void dij(int s,ll *d)
{
    memset(d,0x3f,sizeof(d));
    memset(vis,0,sizeof(vis));
    d[s]=0;
    priority_queue<pair<ll,int>> q;
    q.push(make_pair(0,1));
    vis[s]=1;
    while(!q.empty())
    {
        int u=q.top().second;q.pop();
        // if(u==n)
        //     break;
        if(rg - dk[u] <= 0 && u!=s)
        {
            flag[u]=true;
            continue;
        };
        for(auto v:nb[u])
        {
            if(vis[v])
                continue;
            d[v]=d[u]+max(0ll,rg-dk[v]);
            // printf("%d->%d\n",u,v);
            vis[v]=1;
            q.push(make_pair(-d[v],v));
        };
    }
}

inline ll calc(ll l)
{
    ll ans = (l/rg) * ((rg+1)*rg/2);
    ll k = l%rg;
    ans += (rg+rg+k-1) * k / 2;
    return ans;
}

int main()
{
    scanf("%d %d %d %lld",&n,&m,&k,&rg);
    for(int i=1;i<=m;i++)
    {
        int u,v;scanf("%d %d",&u,&v);
        nb[u].push_back(v);
        nb[v].push_back(u);
    };
    memset(dk,-1,sizeof(dk));
    memset(dt,-1,sizeof(dt));
    bfs(k, dk);
    bfs(n, dt);
    dij(1, ds);
    // for(int i=1;i<=n;i++)
    //     printf("dk[%d]=%lld\n",i,dk[i]);
    // printf("\n");
    // for(int i=1;i<=n;i++)
    //     printf("dt[%d]=%lld\n",i,dt[i]);
    // printf("\n");
    // for(int i=1;i<=n;i++)
    //     printf("ds[%d]=%lld\n",i,ds[i]);
    // printf("\n");

    // printf("flag:\n");
    ll ans=-1;
    for(int u=1;u<=n;u++)
        if(flag[u])
        {
            // printf("%d ",u);
            ll t = ds[u] + calc(dt[u]+1);
            ans = ans==-1?t:min(t,ans);
        };
    // printf("\n");
    printf("%lld\n",ans);
    return 0;
}