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

#define MAXN 200000

using namespace std;

int set_number[MAXN], set_size[MAXN], current_set = 0, max_set_size = 0, max_set_id = 0;
bool in_big_set[MAXN];
vector<int> v[MAXN];

void dfs(int i) {
	set_number[i] = current_set;
	set_size[current_set]++;
	if(set_size[current_set] > max_set_size) {
		max_set_size = set_size[current_set];
		max_set_id = current_set;
	}
	for(int u:v[i])
		if(in_big_set[u] && set_number[u] == 0)
			dfs(u);
}

int main() {
	int n, m, d;
	scanf("%d%d%d", &n, &m, &d)?:0;
	int c[n];
	fill(c, c+n, 0);
	for(int i = 0; i < m; i++) {
		int a, b;
		scanf("%d%d", &a, &b)?:0;
		v[--a].push_back(--b);
		v[b].push_back(a);
		c[a]++;
		c[b]++;
	}
	set<pair<int,int> > s;
	for(int i = 0; i < n; i++)
		s.insert(make_pair(c[i], i));
	int left = n;
	fill(in_big_set, in_big_set+n, true);
	while((*s.begin()).first < d && left > d) {
		int u = (*s.begin()).second;
		for(int x:v[u]) {
			auto it = s.find(make_pair(c[x], x));
			if(it != s.end()) {
				s.erase(it);
				s.insert(make_pair(c[x]-1, x));
			}
			c[x]--;
		}
		s.erase(make_pair(c[u], u));
		in_big_set[u] = false;
		left--;
	}
	if(left <= d) {
		puts("NIE");
		return 0;
	}
	for(int i = 0; i < n; i++)
		if(in_big_set[i] && set_number[i] == 0) {
			current_set++;
			dfs(i);
		}
	printf("%d\n", max_set_size);
	for(int i = 0; i < n; i++)
		if(set_number[i] == max_set_id)
			printf("%d ", i+1);
	puts("");
	return 0;
}