#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];

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});
    }
    vector<bool> viss(n + 1);
    dij(a, pos);
    for (int i = 1; i <= n; i++)
    {
        if (dis[i] == d - 1)
        {
            viss[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++)
    {
        sum[i] = sum[i - 1] + now;
        now--;
        if (now <= 0)
            now = d;
    }
    for (int i = 1; i <= n; i++)
    {
        if (dis[i] < inf)
            w[i] = sum[dis[i]];
        else
            w[i] = inf;
    }
    dij(b, 1);
    int ans = dis[n];
    for (int i = 1; i <= n; i++)
    {
        if (viss[i])
        {
            ans = min(ans, dis[i] + w[i]);
        }
    }
    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});
            }
        }
    }
}