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

typedef unsigned uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii> vpii;
typedef complex<double> cpx;
template <typename T> using minPq = priority_queue<T, vector<T>, greater<T>>;
#define ms(a, x) memset(a, x, sizeof(a))
#define pb push_back
#define fs first
#define sn second
#define ALL(v) begin(v), end(v)
#define SZ(v) ((int) (v).size())
#define lbv(v, x) (lower_bound(ALL(v), x) - (v).begin())
#define ubv(v, x) (upper_bound(ALL(v), x) - (v).begin())
template <typename T> void UNIQUE(vector<T> &v){sort(ALL(v)); v.resize(unique(ALL(v)) - v.begin());}
const int INF = 0x3f3f3f3f;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1);
#define FR(i, n) for(int i = 0; i < (n); i++)
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define FORR(i, a, b) for(int i = (a); i >= (b); i--)
#define dbg(x) {cerr << #x << ' ' << x << endl;}
#define dbgArr(arr, n) {cerr << #arr; FR(_i, n) cerr << ' ' << (arr)[_i]; cerr << endl;}
template <typename T, typename U>
ostream& operator<<(ostream &os, pair<T, U> p){return os << "(" << p.fs << ", " << p.sn << ")";}

const int MN = 1e5 + 5;
int n, m, s, k;
vi adjList[MN];
int disN[MN], disS[MN];
int qu[MN], ql, qr;

ll getCost(int d){
    d++;
    int dv = d/k, rem = d % k;
    return (ll) dv*k*(k+1)/2 + (ll) rem*(k+k-rem+1)/2;
}

void bfs(int src, int *dis){
    fill_n(dis, n, -1);
    dis[src] = 0;
    ql = qr = 0;
    qu[qr++] = src;
    while(ql < qr){
        int n1 = qu[ql++];
        for(int n2 : adjList[n1]) if(dis[n2] == -1) dis[n2] = dis[n1]+1, qu[qr++] = n2;
    }
}

ll cost[MN], dp[MN];

void calcDp(){
    FR(i, n) cost[i] = getCost(disN[i]);

    ms(dp, INF);
    minPq<pair<ll, int>> pq;
    FR(i, n) if(disS[i] == k) dp[i] = cost[i], pq.push({cost[i], i});

    while(!pq.empty()){
        auto [c1, n1] = pq.top(); pq.pop();
        if(c1 != dp[n1]) continue;
        for(int n2 : adjList[n1]) if(disS[n2] < k){
            ll c2 = c1 + k - disS[n2];
            if(c2 < dp[n2]) dp[n2] = c2, pq.push({c2, n2});
        }
    }
}

int main(){
    cin.sync_with_stdio(0); cin.tie(0);
    cin >> n >> m >> s >> k;
    s--;
    FR(i, m){
        int a, b;
        cin >> a >> b;
        a--; b--;
        adjList[a].pb(b);
        adjList[b].pb(a);
    }

    bfs(n-1, disN);
    bfs(s, disS);
    calcDp();

    /*dbgArr(disN, n);
    dbgArr(disS, n);
    dbgArr(cost, n);
    dbgArr(dp, n);*/

    ll ans = LLINF;
    for(int n1 : adjList[0]) ans = min(ans, disS[n1] < k ? dp[n1] : cost[n1]);
    cout << ans << '\n';
}