#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const ll N = 1e5 + 8, M = 2e5 + 8, INF = 0x3f3f3f3f3f3f3f3fll;
ll n, m, k, d;
ll head[N], nxt[M * 2], ver[M * 2], tot;
bitset<N> vis;
ll val[N], dis[N]/* , dn[N] */;

void add(ll u, ll v) { nxt[++tot] = head[u], head[u] = tot, ver[tot] = v; }

void bfs1(ll s)
{
	vis.reset();
	queue<ll> q;
	val[s] = d;
	if(d == 1)
		return;
	q.push(s), vis[s] = true;
	while(!q.empty())
	{
		ll u = q.front(), v;
		q.pop();
		for(ll i = head[u]; i; i = nxt[i])
			if(!vis[v = ver[i]])
			{
				val[v] = val[u] - 1;
				if(val[v] > 1)
					vis[v] = true, q.push(v);
			}
	}
}

void bfs2(ll s)
{
	memset(dis, 0x3f, sizeof(dis));
	if(val[s])
		return;
	queue<ll> q;
	q.push(s), vis[s] = true;
	dis[s] = 0;
	while(!q.empty())
	{
		ll u = q.front(), v;
		q.pop();
		for(ll i = head[u]; i; i = nxt[i])
			if(!vis[v = ver[i]])
			{
				dis[v] = dis[u] + 1;
				vis[v] = true, q.push(v);
			}
	}
}

/* void bfs3(ll s)
{
	vis.reset();
	queue<ll> q;
	q.push(s), vis[s] = true;
	dn[s] = 0;
	while(!q.empty())
	{
		ll u = q.front(), v;
		q.pop();
		for(ll i = head[u]; i; i = nxt[i])
			if(!vis[v = ver[i]])
			{
				dn[v] = dn[u] + 1;
				vis[v] = true, q.push(v);
			}
	}
} */

constexpr ll calc(ll x) { return x * (x + 1) >> 1; }

void dijkstra()
{
	priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> q;
	const ll t = calc(d);
	if(val[n])
	{
		memset(dis, 0x3f, sizeof(dis));
		q.push({dis[n] = 0, n});
	}
	else
	{
		for(ll i = 1; i <= n; i++)
			if(val[i] == 1 && vis[i])
				q.push({(dis[i] = (dis[i] / d + 1) * t - calc(d - dis[i] % d)), i});
			else
				dis[i] = INF;
	}
	vis.reset();
	while(!q.empty())
	{
		ll u = q.top().second, v;
		q.pop();
		if(vis[u])
			continue;
		vis[u] = true;
		for(ll i = head[u]; i; i = nxt[i])
			if(!vis[v = ver[i]] && dis[u] + val[u] < dis[v])
			{
				dis[v] = dis[u] + val[u];
				if(val[v])
					q.push({dis[v], v});
			}
	}
}

int main()
{
	scanf("%lld%lld%lld%lld", &n, &m, &k, &d);
	const ll t = calc(d);
	for(ll i = 1, u, v; i <= m; i++)
		scanf("%lld%lld", &u, &v), add(u, v), add(v, u);
	bfs1(k);
	bfs2(n);
	ll res = (dis[1] == INF) ? INF : ((dis[1] / d + 1) * t - calc(d - dis[1] % d));
	dijkstra();
	printf("%lld\n", min(dis[1], res));
	return 0;
}