#include <bits/stdc++.h>
// #define dd(x) cout << #x << "\n"
#define d(x) cout << #x  << ": " << x << "\n"
using namespace std;
#define int long long
using pii = pair<int, int>;
using vpii = vector<pii>;
using vi = vector<int>;
using vii = vector<vector<int>>;
using a3 = array<int, 3>;
const int inf = 0x3f3f3f3f3f3f3f3fLL;

const int N = 1e5 + 5;
vector<int> full[N];
vector<pair<int, int>> sh[N];
int dis[N], col[N], bd[N], inq[N], dis_sh[N], dis_rev[N];
vector<int> out, in;
int mem[2 * N];

int dddd(int x) {
    return mem[x];
}

void solve() {
    int n, m, k, d; cin >> n >> m >> k >> d;
    {int dx = d;
    for(int i = 1; i <= 2e5; i++) {
        --dx;
        if(dx == 0) dx = d;
        mem[i] = mem[i - 1] + dx;
    }
    }
    
    vector<pair<int, int>> edg(m + 1);
    for(int i = 1; i <= m; i++) {
        int u, v; cin >> u >> v;
        edg[i].first = u, edg[i].second = v;
        full[u].push_back(v);
        full[v].push_back(u);
    }

    {queue<pair<int, int>> Q;
    Q.push({d, k});
    inq[k] = 1;

    while(!Q.empty()) {
        auto [dd, u] = Q.front(); Q.pop();
        dis[u] = dd;
        if(!dd) {
            bd[u] = 1;
            continue;
        }
        col[u] = 1;
        if(dd == 1) in.push_back(u);

        for(auto v : full[u]) {
            if(!inq[v]) {
                inq[v] = 1;
                Q.push({dd - 1, v});
            }
        }
    }
    for(int i = 1; i <= n; i++) {
        if(bd[i]) out.push_back(i);
    }
    }

    {queue<pair<int, int>> Q;
    Q.push({0LL, n});
    memset(inq, 0, sizeof inq);
    inq[n] = 1;

    while(!Q.empty()) {
        auto [ddd, u] = Q.front(); Q.pop();
        dis_rev[u] = ddd;
        for(auto v : full[u]) {
            if(inq[v] || col[v]) continue;
            inq[v] = 1;
            Q.push({ddd + 1, v});
        }
    }}

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> Q;

    for(int i = 1; i <= m; i++) {
        auto [u, v] = edg[i];
        if(col[u] && col[v]) {
            sh[u].push_back({v, dis[v]});
            sh[v].push_back({u, dis[u]});
        }
    }

    int st = 0;
    if(col[1]) {
        st = k;
    } else if(bd[1]) {
        st = n + 1;
        for(auto v : full[1]) {
            if(col[v]) {
                sh[n + 1].push_back({v, 1});
            }
        }
    }

    if(st) {
        memset(dis_sh, 0x3f, sizeof dis_sh);
        dis_sh[st] = 0; Q.push({0, st});

        while(!Q.empty()) {
            auto [d, u] = Q.top(); Q.pop();
            // if(vis[u]) continue; 
            // vis[u] = 1;
            if(dis_sh[u] != d) continue;
            for(auto [v, w] : sh[u]) {
                if(dis_sh[v] > dis_sh[u] + w) {
                    dis_sh[v] = dis_sh[u] + w;
                    Q.push({dis_sh[v], v});
                }
            }
        }
    }

    if(!col[1] && !bd[1]) {
        cout << dddd(dis_rev[1]) << "\n";
        return ;
    }

    auto check = [&]() {
        int pp = 0;
        for(auto u : in) {
            int res = 0;
            for(auto v : full[u]) {
                if(!col[v]) {
                    res = max(res, dis_rev[v]);
                }
            }
            if(res) pp = max({pp, res + dis_sh[u] + d});
        };
        return pp - 1;
    };

    if(col[1]) {
        cout << check() << "\n";
        return ;
    }

    if(bd[1]) {
        cout << min(dddd(dis_rev[1]), check()) << "\n";
        return ;
    }

}


signed main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int T = 1;
    while(T--) solve();
    return 0;
}

/*
5 5 3 1 
1 2
2 4
4 5
1 3
3 5



13 17 12 3
1 2
2 3
3 4
4 13
5 13
7 8
7 9
7 10
7 11
7 6
12 7
1 8
8 9
9 10
10 11
11 6
6 13

*/