#include <bits/stdc++.h>

using namespace std;

int upper(int a, int b)
{
    return (a + b - 1) / b;
}

struct Element
{
    bool isCycle;
    int length;
    Element() {}
    Element(bool b, int l) : isCycle(b), length(l) {}
};

void dfs(vector<vector<int>> & G, vector<bool> & was, int now, int & meetSuper, int & total, int super)
{
    was[now] = true;
    total++;
    for (auto x : G[now])
    {
        if (!was[x])
            dfs(G, was, x, meetSuper, total, super);
        else if (x == super)
            meetSuper++;
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m ,k, x, y;
    cin >> n >> m >> k;
    vector<vector<int>> G(n + 1);
    for (int i = 0; i < m; i++)
    {
        cin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    int super = -1;
    for (int i = 1; i <= n; i++)
        if (G[i].size() > 2)
            super = i;
    if (super == -1)        /// No root, trivial case: chain or loop
    {
        cout << upper(n - k, 2 * k);
        return 0;
    }
    vector<Element> elements;
    vector<bool> was(n + 1, false);
    was[super] = true;
    for (auto x : G[super])
        if (!was[x])
        {
            int meetSuper = 0, total = 0;
            dfs(G, was, x, meetSuper, total, super);
            elements.emplace_back(meetSuper == 2, total);
        }
    int R = n, L = -1;
    while (R - L > 1)
    {
        int M = (R + L) / 2, lenM = 2 * M + 1;
        int overlapse = -1, ans = 0;
        for (auto x : elements)
            if (!x.isCycle)
                overlapse = max(overlapse, ((x.length + M) / lenM) * lenM - x.length - 1);
        if (overlapse == -1)        /// Making hole in super
        {
            ans++;
            overlapse = M;
        }
        for (auto x : elements)
        {
            if (x.isCycle)
                ans += upper(max(0, x.length - 2 * overlapse), lenM);
            else
                ans += upper(max(0, x.length - overlapse), lenM);
        }
        if (ans > k)
            L = M;
        else
            R = M;
    }
    cout << R;
    return 0;
}