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

template <class T> using V = vector<T>;
template <class T> using VV = V<V<T>>;

using ll = int64_t;

int main() {
	ios_base::sync_with_stdio(false), cin.tie(nullptr);
	cout << fixed << setprecision(20);

	int N, M, K, D;
	cin >> N >> M >> K >> D;
	K--;

	VV<int> adj(N);
	for (int e = 0; e < M; e++) {
		int a, b;
		cin >> a >> b;
		a--, b--;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}

	auto get_dist = [&](int st) -> V<int> {
		V<int> q = {st};
		q.reserve(N);
		V<int> dist(N, -1);
		dist[st] = 0;
		for (int z = 0; z < int(q.size()); z++) {
			int cur = q[z];
			for (int nxt : adj[cur]) {
				if (dist[nxt] == -1) {
					dist[nxt] = dist[cur] + 1;
					q.push_back(nxt);
				}
			}
		}
		assert(int(q.size()) == N);
		return dist;
	};

	auto dist_N1 = get_dist(N-1);
	auto dist_K = get_dist(K);

	const ll INF = 1e18;
	V<ll> dist2(N, INF);
	struct Data {
		ll key;
		int i;

		bool operator < (const Data& o) const { return key > o.key; }
	};
	priority_queue<Data> pq;
	auto do_push = [&](int v, ll d) -> void {
		if (d < dist2[v]) {
			dist2[v] = d;
			pq.push(Data{d, v});
		}
	};
	do_push(0, 0);
	while (!pq.empty()) {
		auto [d, cur] = pq.top();
		pq.pop();
		assert(dist2[cur] <= d);
		if (dist2[cur] < d) continue;
		for (int nxt : adj[cur]) {
			if (dist_K[nxt] >= D) continue;
			ll nd = d + (D - dist_K[nxt]);
			do_push(nxt, nd);
		}
	}
	assert(dist2[0] == 0);

	ll ans = INF;
	auto eval = [&](ll d_n1) -> ll {
		d_n1++;
		ll nfull = d_n1 / D;
		ll nrest = d_n1 % D;
		return nfull * D * (D+1) / 2 + nrest * (D + (D-nrest+1)) / 2;
	};
	for (int f = 0; f < N-1; f++) {
		if (dist2[f] == INF) continue;
		for (int g : adj[f]) {
			if (dist_K[g] < D) continue;
			ll cost = dist2[f] + eval(dist_N1[g]);
			//cerr << "(" << f << ", " << g << "): cost = " << cost << endl;
			ans = min(ans, cost);
		}
	}
	assert(ans < INF);
	cout << ans << '\n';

	return 0;
}