#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> pii;
main(){
  ios::sync_with_stdio(false);
  int n,m,k,d,c=1e16; cin>>n>>m>>k>>d;
  vector<vector<int> > g(n);
  for(int i=1;i<=m;i++){
    int u,v; cin>>u>>v;
    g[--u].emplace_back(--v);
    g[v].emplace_back(u);
  }
  auto bfs=[&](int u){
    queue<int> q; q.emplace(u);
    vector<int> d(n);
    vector<bool> b(n); b[u]=true;
    while(!q.empty()){
      int u=q.front(); q.pop();
      for(int i:g[u])
        if(!b[i])b[i]=true,d[i]=d[u]+1,q.emplace(i);
    }
    return d;
  };
  auto s=[](int l,int r){
    return max(0ll,r*(r+1)-l*(l-1)>>1);
  };
  auto f=[&](int x){
    return x/d*s(1,d)+s(d-x%d+1,d);
  };
  vector<int> dk=bfs(k-1),dn=bfs(n-1),l(n,1e16);
  vector<bool> b(n);
  priority_queue<pii,vector<pii>,greater<> > q;
  q.emplace(l[0]=0,0);
  while(!q.empty()){
    int u=q.top().second; q.pop();
    if(b[u])continue; b[u]=true;
    for(int i:g[u])
      if(dk[i]>=d)c=min(c,l[u]+f(dn[i]+1));
      else if(l[u]+d-dk[i]<l[i])q.emplace(l[i]=l[u]+d-dk[i],i);
  }
  cout<<min(c,l[n-1])<<endl;
  return 0;
}