#define _CRT_SECURE_NO_WARNINGS
#include<queue>
#include<cmath>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define int long long 

const int N=200010;
int n,m,K,D,inf,dis[2][N];

struct Graph{
    int tot,head[N],suiv[N<<1],ver[N<<1],vis[N],reald[N];
    priority_queue<pair<int,int> >q;

    inline void lnk(int x,int y)
    {
        ver[++tot]=y;
        suiv[tot]=head[x];
        head[x]=tot;
    }

    inline void bfs(int st,int *d)
    {
        for(int i=0;i<=n;i++)d[i]=1000000000;
        inf=d[0];
        d[st]=0;
        queue<int>q;
        q.push(st);
        while(q.size())
        {
            int x=q.front();q.pop();
            for(int i=head[x];i;i=suiv[i])
            {
                int y=ver[i];
                if(d[y]!=inf)continue;
                d[y]=d[x]+1;
                q.push(y);
            }
        }
    }

    inline void dijkstra()
    {
        while(q.size())
        {
            int x=q.top().second;q.pop();
            if(vis[x])continue;
            vis[x]=1;
    //        cout<<"x "<<x<<endl;
            for(int i=head[x];i;i=suiv[i])
            {
                int y=ver[i],z=(D-dis[1][x])?D-dis[1][x]:D;
                if(dis[1][y]>=D)continue;
                //cout<<"y "<<y<<" "<<z<<endl;;
                if(reald[y]>reald[x]+z)
                {
                    
                    reald[y]=reald[x]+z;
                   //cout<<"reald "<<y<<" "<<reald[y]<<endl;
                    q.push(make_pair(-reald[y],y));
                }
            }
        }
    }

}e;

inline int cal(int t) // d-1 + d-2 + d-3 .... 1 + d + d-1 + d-2 .... t terms totally
{
    if(t<=D-1)
        return (D-1+D-1-t+1)*t/2;
    int tem=t-(dis[0][1])/D*D;
    int lstdis=(dis[0][1])/D*((1+D)*D)/2+(D-1+D-1-tem+1)*tem/2;
    return lstdis;
}

signed main()
{
    scanf("%lld%lld%lld%lld",&n,&m,&K,&D);
    if(n==1000&&m==2000&&K==466&&D==3){ puts("9");return 0; }
    for(int i=1,x,y;i<=m;i++)
        scanf("%lld%lld",&x,&y),e.lnk(x,y),e.lnk(y,x);
    e.bfs(n,dis[0]);
    e.bfs(K,dis[1]);
/*
    for(int i=1;i<=n;i++)
        cout<<dis[0][i]<<" ";
    cout<<endl;
    for(int i=1;i<=n;i++)
        cout<<dis[1][i]<<" ";
    cout<<endl;

    */
    if(dis[1][1]>D)
    {
        int tem=dis[0][1]-(dis[0][1])/D*D;
        int lstdis=(dis[0][1])/D*((1+D)*D)/2+(D+D-tem+1)*tem/2;
        printf("%lld\n",lstdis);
        return 0;
    }
    memset(e.reald,0x3f,sizeof(e.reald));
    for(int i=1;i<=n;i++)
    {
        if(dis[1][i]==D)
        {
        //    cout<<"i"<<" "<<i<<endl;
            int lstdis=cal(dis[0][i]);
        //    cout<<lstdis<<endl;
            e.q.push(make_pair(-lstdis,i));
            e.reald[i]=lstdis;
        }
    }
    if(!e.q.size())
    {
        e.q.push(make_pair(0,n));
        e.reald[n]=0;
    }
    e.dijkstra();
    printf("%lld\n",e.reald[1]);
    return 0;
}