#include<bits/stdc++.h>
using namespace std;
#define int long long  
vector<int> e[100000+10];
int dis[100000+10];
int dis1[100000+10];
int dis2[100000+10];
signed main (){
	std::ios::sync_with_stdio(false);  
	cin.tie(NULL); 
	cout.tie(NULL);
	int n,m,k,d;
	cin>>n>>m>>k>>d;
	memset(dis1,0x3f,sizeof(dis1));
	dis1[1] =0; 
	for(int i=1;i<=m;i++)
	{
		int u,v;
		cin>>u>>v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	queue<int> q;
	q.push(n);
	dis2[n] = 1;
	while(!q.empty())
	{
		auto x=q.front();
		q.pop();
		for(auto v:e[x])
		{
			if(dis2[v])
			continue ;
			else 
			dis2[v] = dis2[x] +1;
			q.push(v);
		}
	}
	q.push(k);
	dis[k] = 1;
	
	while(!q.empty())
	{
		auto x=q.front();
		q.pop();
		for(auto v:e[x])
		{
			if(dis[v])
			continue ;
			else 
			dis[v] = dis[x] +1;
			q.push(v);
			
		}
	}

	q.push(1);
	int ans = LLONG_MAX;
	while(!q.empty())
	{	auto x = q.front();
		q.pop();
		for(auto v:e[x])
		{
			if(dis[v]>d)
			{
				int sub = (dis2[v]-1)%d;
				ans = min(ans,dis1[v]+(dis2[v]-1)/d*(d*(d+1))/2+sub*(sub+1)/2);
			}
			else if(v==n)
			{
				ans = min(ans,dis1[x]+(d-dis[v]+1));
			}
			else if(dis1[v]>dis1[x]+(d-dis[v]))
			{	
				dis1[v] = dis1[x]+(d-dis[v]+1);
				q.push(v);
			}
		}
	}
	cout<<ans<<endl;
	

}