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
#include <cstdio>
#include <vector>
#include <algorithm>

int N,M,D;
bool valid[200100];
bool visited[200100];
int cnt[200100];
std::vector<int> bad;
std::vector<int> edges[200100];

void dfs(int v, std::vector<int> &nodes) {
	visited[v] = true;
	nodes.push_back(v);
	for (int i=0; i<edges[v].size(); ++i) {
		int next = edges[v][i];
		if (valid[next] && !visited[next]) dfs(next, nodes);
	}
}

int main() {
	scanf("%d %d %d",&N,&M,&D);

	for (int i=1;i<=N;++i) {
		cnt[i]=0;
		valid[i]=true;
		visited[i]=false;
	}

	for (int i=0;i<M;++i) {
		int a,b;
		scanf("%d %d",&a,&b);

		cnt[a]++;
		cnt[b]++;
		edges[a].push_back(b);
		edges[b].push_back(a);
	}

	for (int i=1;i<=N;++i) {
		if (cnt[i]<D) {
			valid[i] = false;
			bad.push_back(i);
		}
	}

	while (!bad.empty()) {
		int node = *bad.rbegin();
		bad.pop_back();

		for (int i=0; i<edges[node].size(); ++i) {
			int next = edges[node][i];
			cnt[next]--;

			if (valid[next] && cnt[next]<D) {
				valid[next] = false;
				bad.push_back(next);
			}
		}
	}

	std::vector<int> result;
	for (int i=1; i<=N;++i) {
		if (valid[i] && !visited[i]) {
			std::vector<int> component;
			dfs(i, component);
			if (component.size() > result.size()) result = component;
		}
	}

	if (result.size() > 0) {
		std::sort(result.begin(), result.end());
		printf("%d\n",(int)result.size());
		for (int i=0;i<result.size();++i) printf("%d ",result[i]);
	} else {
		printf("NIE\n");
	}

	return 0;
}