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
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <cstring>
#include <cassert>

using namespace std;

struct sc {
	int s;
	int ip;
	bool full;
	sc(int a, int b, bool c) : s(a), ip(b), full(c) {}
};

int n, m, k;
bool odw[200001];
vector<sc> s[200001];
vector<pair<int, int>> kraw, flip;
vector<int> vodw;
long long wynik[51];

int dfs(int a) {
	if (odw[a]) return 0;
	int udalosie = 0, gdzie = 0;
	odw[a] = 1;
	vodw.push_back(a);
	for (int i = 0; i < (int)s[a].size(); i++) {
		if (s[a][i].full || odw[s[a][i].s]) continue;
		if (s[a][i].s == 0 || dfs(s[a][i].s)) {
			udalosie = 1;
			gdzie = i;
			break;
		}
	}
	
	if (udalosie) {
		int i = gdzie;
		s[a][i].full = true;
		flip.emplace_back(a, i);
		if (s[a][i].ip != -1) {
			s[s[a][i].s][s[a][i].ip].full = false;
			flip.emplace_back(s[a][i].s, s[a][i].ip);
		}
	}
	
	return udalosie;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m >> k;
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		kraw.emplace_back(a, b);
	}
	
	for (const auto &x: kraw) {
		int a = x.first, b = x.second;
		int ia = s[a+n].size(), ib = s[b].size();
		s[a + n].emplace_back(b, ib, true);
		s[b].emplace_back(a + n, ia, false);
	}
		
	for (int i = 1; i <= k; i++) {
		s[i].emplace_back(0, -1, false);
	}
		
	for (int i = 1; i <= n; i++) {
		int ip = s[i].size(), ik = s[i+n].size();
		s[i].emplace_back(i + n, ik, true);
		s[i + n].emplace_back(i, ip, false);
	}
	
	for (int i = k + 1; i <= n; i++) {
		int ile = 0;
		memset(odw + 1, 0, sizeof(bool) * n * 2);
		
		for (const auto &x: flip) {
			s[x.first][x.second].full ^= 1;
		}
		flip.clear();
		
		for (int j = i; j <= n; j++) {
			if (dfs(j + n)) {
				ile++;
				for (int x: vodw) odw[x] = false;
				vodw.clear();
			}
			wynik[ile]++;
		}
	}
	
	for (int i = 0; i <= k; i++) cout << wynik[i] << '\n';
}