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
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
#include <bits/stdc++.h>                                                        
using namespace std;                                                            
const int maxn = 1000;                                                          
typedef long long ll;                                                           
typedef pair<int, int> Pii;                                                     
typedef vector<Pii> vpii;                                                       
typedef vector<int> vi;                                                         
typedef vector<ll> vll;                                                         
#define pb push_back                                                            
#define fst first                                                               
#define snd second                                                              
int n, m, k;                                                                    
vi E[maxn];                                                                     
vi Erev[maxn];                                                                  
int resl[maxn];                                                                 
int resr[maxn];                                                                 
int wyn[maxn];                                                                  
vi wierz[maxn];                                                                 
vi wierzrev[maxn];                                                              

int res;                                                                        
bool wyjebane[maxn];                                                            

void przelicz(int level)                                                        
{                                                                               
    for(int x : wierz[level])                                                   

        if(wyjebane[x])                                                         
            resl[x] = 0;                                                        
        else                                                                    
        {                                                                       
            resl[x] = 1;                                                        
            for(int y : Erev[x])                                                
                resl[x] = max(resl[x], resl[y] + 1);                            
        }                                                                       
    for(int x : wierzrev[level])
        if(wyjebane[x])                                                         
            resr[x] = 0;                                                        
        else                                                                    
        {                                                                       
            resr[x] = 1;                                                        
            for(int y : E[x])                                                   

                resr[x] = max(resr[x], resr[y] + 1);                            
        }                                                                       
    for(int x : wierz[level])                                                   
        wyn[x] = resl[x] + resr[x] - 1;                                         
}                                                                               
typedef array<int, 4> mk;
mk mama_kaszuby;
vector<mk> do_przeliczenia[maxn];
void backtracz(int level, int wyjebane_k)                                       
{                                                                               
    if(level == 1)                                                              
    {                                                                           
        puts("1");                                                              
        exit(0);                                                                
    }
    if(wyjebane_k == k)                                                                           
	{
		mk tata_kaszuby = mama_kaszuby;
		sort(&tata_kaszuby[0], &tata_kaszuby[0] + 4);
		do_przeliczenia[level].pb(tata_kaszuby);
		return;
	}
	przelicz(level);                                                            
    vi rowne;                                                                   
    for(int x : wierz[level])                                                   
        if(wyn[x] == level)                                                     
            rowne.pb(x);                                                        
    if(rowne.empty())                                                           
        backtracz(level-1, wyjebane_k);                                         
    else                                                                        
    {                                                                           
        if(wyjebane_k == k)                                                     
            res = min(res, level);                                              
        else                                                                    
        {                                                                       
            for(int x : rowne)                                                  
            {                                                                   
                wyjebane[x] = true;
                mama_kaszuby[wyjebane_k] = x;                                             
                backtracz(level, wyjebane_k + 1);                               
                wyjebane[x] = false;                                            
            }                                                                   
        }                                                                       
    }                                                                           
}
                                         
int main()                                                                      
{               
	mama_kaszuby[0] = mama_kaszuby[1] = mama_kaszuby[2] = mama_kaszuby[3] = 1000;                                                                
    scanf("%d%d%d", &n, &m, &k);                                                
    if(n == k)                                                                  
    {                                                                           
        puts("0");                                                              
        return 0;                                                               
    }                                                                           
    for(int i = 0; i < m; ++i)                                                  
    {                                                                           
        int a, b;                                                               
        scanf("%d%d", &a, &b);                                                  
        --a; --b;                                                               
        E[a].pb(b);                                                             
        Erev[b].pb(a);                                                          

    }                                                                           
    for(int i = 0; i < n; ++i)                                                  
    {                                                                           
        wierz[0].pb(i);                                                         
        wierzrev[0].pb(n - 1 - i);                                              
    }                                                                           
    przelicz(0);                                                                
                                                                                
    for(int i = 0; i < n; ++i)                                                  
        for(int j = 1; j <= wyn[i]; ++j)                                        
            wierz[j].pb(i);                                                     

    for(int i = 0; i < n; ++i)                                              
        wierzrev[i] = vi(wierz[i].rbegin(), wierz[i].rend());                   
    int mx = 0;                                                                 
    for(int i = 0; i < n; ++i)                                                  
        mx = max(mx, wyn[i]);                                                   
    res = mx;        
    backtracz(mx, 0);
    for(int i = n; i >= 0; --i)
    {
		//sum += do_przeliczenia[i].size();
		sort(do_przeliczenia[i].begin(), do_przeliczenia[i].end());
		int sz = do_przeliczenia[i].size();
		for(int j = 0; j < sz; ++j)
			if(j == 0 || do_przeliczenia[i][j] != do_przeliczenia[i][j-1])
			{
				for(int dupa = 0; dupa < k; ++dupa)
					wyjebane[do_przeliczenia[i][j][dupa]] = true;
				
				przelicz(i);
				int ma = 0;
				for(int x : wierz[i])
					if(!wyjebane[x])
						ma = max(ma, wyn[x]);
				if(ma < i)
					do_przeliczenia[i-1].pb(do_przeliczenia[i][j]);
				
				res = min(res, i);
				for(int dupa = 0; dupa < k; ++dupa)
					wyjebane[do_przeliczenia[i][j][dupa]] = false;
			}
	}
    printf("%d\n", res);                                                        
}