#include <iostream>
#include <algorithm>
#include <vector>
#include <stdio.h>

using namespace std;

vector<int> dag_longest_path(const vector<vector<int>>& succ) {
    vector<pair<int, int>> lens(succ.size(), {0, -1});
    pair<int, int> mx(0, -1);
    for (int i = 0; i < succ.size(); i++) {
        int d = lens[i].first + 1;
        for (int s : succ[i]) {
            if (lens[s].first < d) {
                lens[s].first = d;
                lens[s].second = i;
                if (mx.first < d) {
                    mx.first = d;
                    mx.second = s;
                }
            }
        }
    }
    vector<int> res;
    pair<int, int> cur = mx;
    while (cur.second != -1) {
        res.push_back(cur.second);
        cur = lens[cur.second];
    }
    reverse(res.begin(), res.end());
    return res;
}

int brute(vector<vector<int>>& succ, int k) { //copy - for now... or not
    vector<int> path = dag_longest_path(succ);
    int res = path.size();
    if (k > 0) {
        for (int v : path) {
            vector<int> tmp;
            swap(succ[v], tmp);
            int r = brute(succ, k - 1);
            if (res > r)
                res = r;
            swap(succ[v], tmp);
        }
    }
    return res;
}

int main() {
    std::ios_base::sync_with_stdio(0);

    int n, m, k;
    cin >> n >> m >> k;
    vector<vector<int>> succ(n);
    while (m--) {
        int x, y;
        cin >> x >> y;
        x--;
        y--;
        succ[x].push_back(y);
    }

    int res = brute(succ, k);

    cout << res << endl;
}