1. 1
2. 2
3. 3
4. 4
5. 5
6. 6
7. 7
8. 8
9. 9
10. 10
11. 11
12. 12
13. 13
14. 14
15. 15
16. 16
17. 17
18. 18
19. 19
20. 20
21. 21
22. 22
23. 23
24. 24
25. 25
26. 26
27. 27
28. 28
29. 29
30. 30
31. 31
32. 32
33. 33
34. 34
35. 35
36. 36
37. 37
38. 38
39. 39
40. 40
41. 41
42. 42

#include <bits/stdc++.h>
using namespace std;
constexpr int MAXN = 100001;

int c[MAXN];
vector<int> G[MAXN];

int cnt, scc_num, scc[MAXN], in[MAXN], low[MAXN];
stack<int> s;
bitset<MAXN> ins;

void tarjan(int u) {
	low[u] = in[u] = cnt++;
	s.push(u);
	ins[u] = 1;
	for (int v : G[u]) {
		if (in[v] == -1) tarjan(v), low[u] = min(low[u], low[v]);
		else if (ins[v]) low[u] = min(low[u], in[v]);
	}
	if (low[u] == in[u]) {
		++scc_num;
		while (1) {
			int x = s.top(); s.pop();
			scc[x] = scc_num, ins[x] = 0;
			if (x == u) break;
		}
	}
}

int main() {
	int N, M, K; cin >> N >> M >> K;
	while (M--) {
		int a, b; cin >> a >> b;
		G[a].push_back(b);
	}

	memset(scc, -1, sizeof scc), memset(in, -1, sizeof in);
	for (int u = 1; u <= N; ++u) if (scc[u] == -1) tarjan(u);

	if (scc_num < K) cout << "impossible\n";
	else for (int u = 1; u <= N; ++u) cout << min(scc[u], K) << '\n';	
}