#include<bits/stdc++.h>
#define ll long long
#define re register
using namespace std;

inline int read()
{
	int f=1,x=0;char s=getchar();
	while(s<'0'||s>'9')
	{
		if(s=='-') f=-1;
		s=getchar();
	}
	while(s>='0'&&s<='9')
	{
		x=x*10+s-48;
		s=getchar();
	}
	return f*x;
}

const int N=2e5+5;
vector<int> e[N];
int disk[N],disn[N];
ll dis[N];
queue<int> q;
int vis[N];
int n,m,k,d;
const ll INF=1ll<<60;

void bfs(int s,int *dis)
{
	for(int i=1;i<=n;i++) vis[i]=0;
	for(int i=1;i<=n;i++) dis[i]=1e9;
	dis[s]=0,vis[s]=1;
	q.push(s);
	while(!q.empty())
	{
		int x=q.front();q.pop();
		for(int y:e[x])
		{
			if(vis[y]) continue;
			vis[y]=1;
			dis[y]=dis[x]+1;
			q.push(y);
		}
	}
}

struct node
{
	int pos;
	ll val;
	friend bool operator < (node a,node b)
	{
		return a.val>b.val;
	}
};

priority_queue<node> Q;

void solve()
{
	ll ans=INF;
	for(int i=1;i<=n;i++) vis[i]=0;
	for(int i=1;i<=n;i++) dis[i]=INF;
	Q.push({1,0});
	dis[1]=0;
	while(!Q.empty())
	{
		auto res=Q.top();Q.pop();
		int x=res.pos;
		if(vis[x]) continue;
		vis[x]=1;
//		cout<<x<<" "<<val<<endl;
		for(int y:e[x])
		{
			if(disk[y]>=d)
			{
//				cout<<y<<" "<<x<<" "<<	dis[x]<<endl;
				ll sum=dis[x]+d-disk[x];
				int len=disn[y]+1;
				int t=len/d,b=len%d;
				sum+=1ll*t*d*(d+1)/2;
				sum+=1ll*(d+d-b+1)*b/2;
//				cout<<sum<<endl;
				ans=min(ans,sum);
				continue;
			}
			if(dis[y]>dis[x]+d-disk[x])
			{
				dis[y]=dis[x]+d-disk[x];
				Q.push({y,dis[y]});
			}
		}
	}
	printf("%lld\n",min(ans,dis[n]));
} 

int main()
{
	n=read(),m=read(),k=read(),d=read();
	for(int i=1;i<=m;i++) 
	{
		int a=read(),b=read();
		e[a].push_back(b);
		e[b].push_back(a);
	}
	bfs(k,disk);
	bfs(n,disn);
//	for(int i=1;i<=n;i++) cout<<disk[i]<<endl;
	solve();
	return 0;
}