#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read() {
    int x = 0, f = 1; char ch = getchar();
    while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
    while(ch>='0'&&ch<='9') { x=(x<<3)+(x<<1)+(ch^48); ch=getchar(); }
    return x * f;
}
typedef long long LL;
const int N = 1e5+7;
int n,m,k,d;
int col[N];
int cnt;
int head[N];
struct Edge {
	int next, to;
} edge[N<<1];
void add(int u,int v) {
	edge[++cnt] = (Edge){head[u], v};
	head[u] = cnt;
}
vector<int> whi;
void Colbfs() {
	memset(col, -1, sizeof(col));
	queue<int> q;
	q.emplace(k); col[k] = d;
	while(!q.empty()) {
		int u = q.front(); q.pop();
		for(int i=head[u];i;i=edge[i].next) {
			int v = edge[i].to;
			if(col[u] == 1) {
				if(col[v] != -1) continue;
				whi.emplace_back(v);
				col[v] = 0;
				continue;
			}
			if(col[v] == -1) {
				col[v] = col[u] - 1;
				q.emplace(v);
			}
		}
	}
}
int cld[N],dis[N];
bool vis[N];	//dijkstra µÄvis
void ColDijkstra() {
	memset(cld, 1, sizeof(cld));	//INF
	priority_queue<pair<int,int> > q;
	q.emplace(-0, 1); cld[1] = 0;
	while(!q.empty()) {
		int u = q.top().second; q.pop();
		for(int i=head[u];i;i=edge[i].next) {
			int v = edge[i].to;
			if(col[v] == -1) continue;
			if(cld[u]+col[v] < cld[v]) {	//col[v] ¼´±ßȨ
				cld[v] = cld[u] + col[v];
				q.emplace(-cld[v], v);
			}
		}
	}
}
void Bfs() {
	queue<int> q;
	q.emplace(n);
	dis[n] = 1;
	while(!q.empty()) {
		int u = q.front(); q.pop();
		for(int i=head[u];i;i=edge[i].next) {
			int v = edge[i].to;
			if(!dis[v]) {
				dis[v] = dis[u] + 1;
				q.emplace(v);
			}
		}
	}
}
int f[N];
void Init() {
	for(int i=1;i<=n;++i) {	//nÊÇ×µÄ·¾¶
		f[i] = f[i-1] + d - ((i-1)%d);
	}
}
int get(int x) {
	return f[x];
}
signed main()
{
	n = read(), m = read(), k = read(), d = read();
	for(int i=1;i<=m;++i) {
		int u = read(), v = read();
		add(u, v), add(v, u);
	}
	//puts("read!");
	Colbfs();
	//puts("col!");
	//printf("%d\n",col[1]);
	//for(auto x : whi) printf("%d ",x);
	ColDijkstra();
	//puts("Dijk!");
	//printf("%d %d %d %d %d\n",cld[8], cld[7], cld[12], cld[6], cld[13]);
	Bfs();
	//printf("%d %d\n",dis[13], dis[1]);
	//printf("n->!");
	Init();
	//printf("%d\n",get(4));
	int ans = 1e18;
	if(col[1] > -1) {
		if(col[n] > 0) {
			ans = min(ans, cld[n]);
		}
		for(auto w : whi) {
			ans = min(ans, cld[w]+get(dis[w]));
		}
	} else {
		ans = get(dis[1]);
	}
	printf("%lld\n",ans);
	return 0;
}
/*
5 5 3 1
 1 2
 2 4
 4 5
 1 3
 3 5
*/