#include <bits/stdc++.h>
using namespace std;
#define int long long
struct dijkstra
{
    int n;
    vector<vector<pair<int, int>>> &G;
    vector<int> distance;

    void build(int &s)
    {
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
        q.emplace(0, s);
        while (!q.empty())
        {
            auto [d, u] = q.top();
            q.pop();
            if (d > distance[u])
            {
                continue;
            }
            for (auto &it : G[u])
            {
                auto [v, w] = it;
                if (distance[v] > d + w)
                {
                    distance[v] = d + w;
                    q.emplace(distance[v], v);
                }
            }
        }
    }

  public:
    dijkstra(int start, vector<vector<pair<int, int>>> &a) : G(a), n(a.size())
    {
        distance = vector<int>(n + 1, LONG_LONG_MAX / 4);
        distance[start] = 0;
        build(start);
    };
    int dis(int end)
    {
        return distance[end];
    }
};
struct graphy
{
    vector<vector<pair<int, int>>> g;
    int n;
    graphy(int n) : n(n)
    {
        g.resize(n + 1);
    }
    void add(int u, int v, int w)
    {
        g[u].emplace_back(v, w);
    }
};
int solve()
{
    int n, m, pos, d;
    cin >> n >> m >> pos >> d;
    graphy g(n);
    for (int i = 0; i < m; i++)
    {
        int u, v;
        cin >> u >> v;
        g.add(u, v, 1);
        g.add(v, u, 1);
    }
    vector<int> sum(n + 1);
    int now = d - 1;
    sum[0] = d;
    if (now <= 0)
    {
        now = d;
    }
    for (int i = 1; i <= n; i++)
    {
        sum[i] = sum[i - 1] + now--;
        if (now <= 0)
        {
            now = d;
        }
    }
    dijkstra d1(n, g.g);
    dijkstra d2(pos, g.g);
    queue<int> q;
    vector<bool> vis(n + 1);
    graphy g2(n);
    vis[pos] = true;
    q.emplace(pos);
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (auto &it : g.g[u])
        {
            auto [v, w] = it;
            if (!vis[v] && d2.dis(v) < d)
            {
                vis[v] = true;
                q.emplace(v);
            }
        }
    }
    for (int i = 1; i <= n; i++)
    {
        if (vis[i])
        {
            for (auto &it : g.g[i])
            {
                auto [v, w] = it;
                if (vis[v])
                {
                    g2.add(i, v, d - d2.dis(v));
                    g2.add(v, i, d - d2.dis(i));
                }
            }
        }
    }
    if (!vis[1])
    {
        for (auto it : g.g[1])
        {
            auto [v, w] = it;
            if (vis[v])
            {
                g2.add(1, v, d - d2.dis(v));
            }
        }
    }
    dijkstra d3(1, g2.g);
    while (!q.empty())
    {
        q.pop();
    }
    q.emplace(pos);
    int ans = LONG_LONG_MAX / 2;
    vis = vector<bool>(n + 1);
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (auto &it : g.g[u])
        {
            auto [v, w] = it;
            if (!vis[v] && d2.dis(v) < d)
            {
                vis[v] = true;
                q.emplace(v);
            }
            if (d2.dis(v) == d)
            {
                ans = min(ans, sum[d1.dis(v)] + d3.dis(u));
            }
        }
    }
    if (ans > 1e12)
    {
        for (auto it : g.g[1])
        {
            ans = min(ans, sum[d1.dis(it.first)]);
        }
    }
    cout << ans << endl;

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