#include <bits/stdc++.h>

#define int ll
using ll = long long;

// #define MING_LE

const int mod = 998244353;
const int inf = 1e18;

using namespace std;

struct info
{
    int to;
    int w;
};

struct node
{
    int dis;
    int u;

    bool operator>(const node &o) const
    {
        return dis > o.dis;
    }
};

int n, m;
int pos, d;

vector<vector<info>> a;
vector<vector<info>> b;
int dis[100010];
int w[100010];
int sum[100010];
bool vis[100010];
bool vlid[100010];
bool in[100010];

void dij(vector<vector<info>> &e, int st);
void solve();

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int __ = 1;
    // cin >> __;

    while (__--)
        solve();

    return 0;
}

void solve()
{
    cin >> n >> m >> pos >> d;
    a.resize(n + 5);
    b.resize(n + 5);
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        a[u].push_back({v, 1});
        a[v].push_back({u, 1});
    }

    dij(a, pos);
    for (int i = 1; i <= n; i++)
    {
        if (dis[i] == d - 1)
            vlid[i] = 1;
        if (dis[i] < d)
            in[i] = 1;
        for (auto it : a[i])
        {
            int to = it.to;
            if (dis[to] >= d)
                continue;
            b[i].push_back({to, d - dis[to]});
        }
    }
    dij(a, n);
    sum[0] = 0;
    int now = d;
    for (int i = 1; i <= n; i++)
    {
        now--;
        if (now <= 0)
            now = d;
        sum[i] = sum[i - 1] + now;
    }
    for (int i = 1; i <= n; i++)
    {
        if (dis[i] < inf)
            w[i] = sum[dis[i]];
        else
            w[i] = inf;
    }
    int ans = 0;
    now = d;
    for (int i = 1; i <= dis[1]; i++)
    {
        ans += now;
        now--;
        if (now <= 0)
            now = d;
    }

    dij(b, 1);

    ans = min(w[1], ans);
    for (int i = 1; i <= n; i++)
    {
        if (vlid[i])
        {
            for (auto it : a[i])
                if (!in[it.to])
                    ans = min(ans, dis[i] + w[it.to] + d);
        }
#ifdef MING_LE
        cout << i << " " << dis[i] << " " << w[i] << '\n';
#endif
    }
    cout << ans << '\n';
}

void dij(vector<vector<info>> &e, int st)
{
    for (int i = 1; i <= n; i++)
    {
        vis[i] = 0;
        dis[i] = inf;
    }

    dis[st] = 0;
    priority_queue<node, vector<node>, greater<node>> q;
    q.push({dis[st], st});

    while (!q.empty())
    {
        int x = q.top().u;
        q.pop();

        if (vis[x])
            continue;
        vis[x] = 1;

        for (auto it : e[x])
        {
            int u = it.to, w = it.w;

            if (dis[u] > dis[x] + w)
            {
                dis[u] = dis[x] + w;
                q.push({dis[u], u});
            }
        }
    }
}

/*
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
*/

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

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

/*
6 7 2 3
1 2
1 3
2 4
3 4
4 6
2 5
5 6
*/

/*
20 26 4 4
1 2
2 3
3 4
4 5
5 6
6 19
4 8
4 9
4 10
4 11
4 12
4 13
1 14
14 8
14 15
15 9
15 16
16 10
16 17
17 11
17 18
18 12
18 7
7 13
19 7
19 20
*/