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
#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define per(i, a, b) for (int i = b; a <= i; i--)
#define cat(x) cerr << #x << " = " << x << '\n';
using ll = long long;
using namespace std;

static constexpr int INF = 1e9;
int nn;
struct Edge {
	int to, cap;
	Edge(int to, int cap) : to(to), cap(cap) {}
};
std::vector<Edge> e;
std::vector<std::vector<int>> g;
std::vector<int> cur, h;
void init(int n) {
	nn = n;
	e.clear();
	g.resize(n);
	for (int i = 0; i < n; i++) {
		g[i].clear();
	}
}
bool bfs(int s, int t) {
	h.assign(nn, -1);
	std::queue<int> que;
	h[s] = 0;
	que.push(s);
	while (!que.empty()) {
		int u = que.front();
		que.pop();
		for (int i : g[u]) {
			auto [v, c] = e[i];
			if (c > 0 && h[v] == -1) {
				h[v] = h[u] + 1;
				if (v == t)
					return true;
				que.push(v);
			}
		}
	}
	return false;
}
int dfs(int u, int t, int f) {
	if (u == t)
		return f;
	int r = f;
	for (int &i = cur[u]; i < int(g[u].size()); ++i) {
		int j = g[u][i];
		auto [v, c] = e[j];
		if (c > 0 && h[v] == h[u] + 1) {
			int a = dfs(v, t, std::min(r, c));
			e[j].cap -= a;
			e[j ^ 1].cap += a;
			r -= a;
			if (r == 0)
				return f;
		}
	}
	return f - r;
}
void addEdge(int u, int v, int c) {
	g[u].push_back(e.size());
	e.emplace_back(v, c);
	g[v].push_back(e.size());
	e.emplace_back(u, 0);
}
int maxFlow(int s, int t) {
	int ans = 0;
	while (bfs(s, t)) {
		cur.assign(nn, 0);
		ans += dfs(s, t, INF);
	}
	return ans;
}

int n, m, k;
vector<pair<int, int>> edges;
ll res[51];

int calculate(int l, int r) {
	init(2 * n + 2);
	int s = 2 * n;
	int t = 2 * n + 1;
	rep(i, 0, n - 1)
		addEdge(2 * i, 2 * i + 1, 1);
	for (auto [a, b] : edges)
		addEdge(2 * a + 1, 2 * b, 1);
	rep(i, 0, k - 1)
		addEdge(s, 2 * i, 1);
	rep(i, l, r)
		addEdge(2 * i + 1, t, 1);
	return maxFlow(s, t);
}

void solve(int start, int l, int r, int a, int b) {
	if (l > r)
		return;
	if (a == b) {
		res[a] += r - l + 1;
		return;
	}
	int m = (l + r) / 2;
	int cur = calculate(start, m);
	res[cur]++;
	solve(start, l, m - 1, a, cur);
	solve(start, m + 1, r, cur, b);
}

int main() {
	cin.tie(0)->sync_with_stdio(0);

	cin >> n >> m >> k;
	while (m--) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		edges.push_back({a, b});
	}

	rep(i, k, n - 1) 
		solve(i, i, n - 1, 0, k);

	rep(i, 0, k)
		cout << res[i] << '\n';
	return 0;
}