1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef long double LD;
typedef pair < int, int > PII;
typedef pair < LL, LL > PLL;
typedef pair < LD, LD > PDD;

#define _upgrade ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
template < typename _T > inline void _DBG(const char *s, _T x) { cerr << s << " = " << x << "\n"; }
template < typename _T, typename... args > void _DBG(const char *s, _T x, args... a) { while(*s != ',') cerr << *s++; cerr << " = " << x << ','; _DBG(s + 1, a...); }

#ifdef LOCAL
#define DBG(...) _DBG(#__VA_ARGS__, __VA_ARGS__)
#define __gcd gcd
#else
#define DBG(...) (__VA_ARGS__)
#define cerr if(0) cout
#endif

// ********************** CODE ********************** //

const int N = 303;

int n, m, k, dp[N], last[N], mn;
bool already[N][N];
vector < int > G[N];

bool blocked[N];

vector < int > get()
{
    bool flag = false;
    vector < int > ans;
    for(int v = 1; v <= n; v++)
    {
        dp[v] = last[v] = 0;
        if(blocked[v]) {
            dp[v] = -1;
            continue;
        }
        flag = true;
        for(auto u: G[v])
        {
            if(!blocked[u] && dp[v] < dp[u] + 1)
            {
                dp[v] = dp[u] + 1;
                last[v] = u;
            }
        }
    }
    if(!flag)
    {
        return ans;
    }
    int id = max_element(dp + 1, dp + n + 1) - dp;
    while(id != 0)
    {
        ans.push_back(id);
        id = last[id];
    }
    return ans;
}

void Go(int x)
{
    vector < int > vec = get();
    mn = min(mn, sz(vec));
    if(x == 0)
        return;
    for(auto v: vec)
    {
        blocked[v] = true;
        Go(x - 1);
        blocked[v] = false;
    }
}

int main()
{
    _upgrade
    cin >> n >> m >> k;
    mn = n + 7;
    for(int i = 0; i < m; i++)
    {
        int a, b; cin >> a >> b;
        if(already[a][b]) continue;
        already[a][b] = true;
        G[b].push_back(a);
    }
    Go(k);
    cout << mn << "\n";
	return 0;
}