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
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;

#define MAX_N 200*1000

int deg[MAX_N + 1];
vector<int> e[MAX_N + 1];

int p[MAX_N + 1];
int cnt[MAX_N + 1];

void dfs(int v, const int &parent)
{
	p[v] = parent;
	++cnt[parent];
	for (int i = 0; i < e[v].size(); ++i)
		if (e[e[v][i]].size() > 0 && p[e[v][i]] == 0)
			dfs(e[v][i], parent);
}

int main()
{
	int n, m, d, cand=0;
	scanf("%d %d %d", &n, &m, &d);
	for (int i = 0; i < m; ++i) {
		int a, b;
		scanf("%d %d", &a, &b);
		e[a].push_back(b);
		++deg[a];
		e[b].push_back(a);
		++deg[b];
	}
	cand = n;
	queue<int> q;
	for (int i = 1; i <= n; ++i) {
		if (deg[i] < d) {
			if (deg[i] == 0)
				--cand;
			else
				q.push(i);
		}
	}
	while (!q.empty() && d < cand) {
//		printf("q.front() = %d, cand = %d\n", q.front(), cand);
		if (e[q.front()].size() != 0) {
			for (int i = 0; i < e[q.front()].size(); ++i) {
				--deg[e[q.front()][i]];
				if (deg[e[q.front()][i]] < d)
					q.push(e[q.front()][i]);
			}

			e[q.front()].clear();
			deg[q.front()] = 0;
			--cand;
		}
		q.pop();
	}
	if (cand <= d) {
		printf("NIE\n");
		return 0;
	}
	// debug
//	printf("---\n");
//	for (int i = 1; i <= n; ++i)
//		printf("%d\n", deg[i]);
//	printf("---\n");
	// znajdz najwiekszy spojny zbior i go wypisz
	vector<int> res;
	for (int i = 1; i <= n; ++i) {
		if (p[i] == 0)
			dfs(i, i);
	}
	int max_size = 0, max_p;
	for (int i = 1; i <= n; ++i) {
		if (max_size < cnt[i]) {
			max_size = cnt[i];
			max_p = i;
		}
	}
	printf("%d\n", max_size);
	for (int i = 1; i <= n; ++i)
		if (p[i] == max_p)
			printf("%d ", i);
	printf("\n");
	return 0;
}