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

char ch;

inline void read(int &x) {
	while(!isdigit(ch = getchar_unlocked()));
	x = ch-'0';	
	while( isdigit(ch = getchar_unlocked())) x *= 10, x += ch-'0';
}

const int MAXN = 200000;
vector<int> g[MAXN + 1];
int deg[MAXN + 1];

inline void add_edge(int a, int b) {
	g[a].push_back(b);
	g[b].push_back(a);
	++deg[a]; ++deg[b];
}

void bfs(int v, int d, vector<int>& res) {
	queue<int> q;
	q.push(v); deg[v] = -1; res.push_back(v);
	while(!q.empty()) {
		int t = q.front(); q.pop();
		for(auto e : g[t]) if(deg[e] >= d) {
			q.push(e); deg[e] = -1; res.push_back(e);
		}
	}
}

void find_set(int n, int d, vector<int>& res) {
	vector<int> bag;
	for(int i = 1; i <= n; ++i) if(deg[i] < d) bag.push_back(i);
	while(!bag.empty()) {
		int v = bag.back(); bag.pop_back();
		for(auto e : g[v]) {
			if(deg[e] == d) bag.push_back(e);
			--deg[e];
		}
	}
	vector<int> t;
	for(int i = 1; i <= n; ++i) if(deg[i] >= d) {
		t.clear();
		bfs(i, d, t);
		if(t.size() > res.size()) res = t;
	}
}

int main() {
	int n, m, d, a, b;
	read(n); read(m); read(d);
	for(int i = 0; i < m; ++i) {
		read(a); read(b);
		add_edge(a, b);
	}
	vector<int> res;
	find_set(n, d, res);
	if(res.empty()) {
		printf("NIE\n");
	} else {
		printf("%d\n", res.size());
		for(int i = 0; i < res.size(); ++i) printf("%d%c", res[i], i + 1 == n ? '\n' : ' ');
	}
	return 0;
}