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
152
153
154
155
156
157
158
159
#include <iostream>
#include <ostream>
#include <map>
#include <vector>

using namespace std;

class Tech;

int maxDepth=0;

class Tech {
public:
	int number;
	// Bezpośrednie zalezności dla technologii
	vector<Tech*> depends;
	// Co można zrobić dzięki technologii
	vector<Tech*> allows;
	/** Ilość testów tego */
	int checked;
	/** Głębokość tego */
	int depth;
	/** Czy testowo usunięty */
	bool removed;
	/** Ilość zależnych węzłów usunięta */
	int dependsRemoved;
public:
	Tech() {}

public:
	void init(int nr) {
		depth = 0;
		checked = 0;
		number = nr;
		removed=false;
		dependsRemoved=0;
	}

	bool reset() {
	    depth=0;
	    checked=0;
	    if(removed) return false;
	    return depends.size()==dependsRemoved;
	}

	// Czy to technologia końcowa - nie ma nic z niej */
	inline bool isEnding() const { return allows.empty(); }

	// Czy to technologia podstawowa - nie wymaga niczego */
	inline bool isBasic() const { return (depends.size()-dependsRemoved)==0; }

	// funkcja do rekurecyjnego obliczania głębokości
	void depthCalc(int depth) {
	    if(removed) return;
        ++depth;
	    if(this->depth<depth) this->depth=depth;

		if (++checked < (depends.size()-dependsRemoved) ) return;    // przetwarzamy gdy były wszystkie próby

		if(this->depth>maxDepth) maxDepth=this->depth;
		for (auto i : allows) i->depthCalc(this->depth);
	}

	void remove() {
	    // oznaczamy jako usunięty
	    removed=true;
		for(auto i : allows) i->dependsRemoved++;
	}

	void unremove() {
	    removed=false;
	    for(auto i : allows) i->dependsRemoved--;
	}
};

ostream& operator<<(ostream &strm, const Tech &t) {
	return strm << "Node[" << t.number << "] is basic=" << t.isBasic() << " is ending=" << t.isEnding() << " depth=" << t.depth;
}

/** Tablica na całość danych */
Tech techs[305];
/** Dynamiczna tablica z technologiami podstawowymi */
vector<Tech*> basic;
/** Rozmiar drzewa */
int n;
/** Ilość elementów do usunięcia */
int k;

/**
 * Funkcja sprawdza rozmiar drzewa dla aktualnej wersji
 * @return
 */
int checkSize() {
    basic.clear();
    for(int i=1;i<=n;++i) {
        Tech* t=&techs[i];
        if(t->reset()) basic.push_back(t);
    }
    maxDepth=0;
    for(auto i : basic) {
        i->depthCalc(0);
    }
    return maxDepth;
}

int probe(int techRemove, int removedCount) {
    if(removedCount==k) return checkSize();
    ++removedCount;
    int best=10000;
    const int to=n-(k-removedCount);
    for(int i=techRemove+1;i<=to;++i) {
        Tech* t=&techs[i];
        t->remove();
        int res=probe(i, removedCount);
        if(res<best) best=res;
        t->unremove();
    }
    return best;
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	// oczytujemy dane wejściowe
	int m;
	cin >> n >> m >> k;

	for (int i = 0; i <= n; ++i) {
		techs[i].init(i);
	}

	// odczytujemy zależności
	for (int i = 0; i < m; ++i) {
		int x, y;
		cin >> x >> y;

		Tech *tx = &techs[x];
		Tech *ty = &techs[y];

		tx->allows.push_back( ty );
		ty->depends.push_back( tx );
	}

	if(k>=n) {	// szczególny przypadek
		cout<<"0"<<endl;
		return 0;
	}

	if(k==0) {
	    cout<<checkSize()<<endl;    // po prostu sprawdzenie rozmiaru gdy k=0.
	    return 0;
	}

	cout<<probe(0, 0)<<endl;

	return 0;
}