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
89
90
91
92
#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>

#define D(x)
#define dout cout

using namespace std;
#define MAX 200100
int n,m,d,a,b;

vector<int> V[MAX];
int ile[MAX];
int G[MAX];

int main()
{
	scanf("%d %d %d",&n,&m,&d);
	for(int i=0;i<m;i++) {
		scanf("%d %d", &a, &b);
		ile[a]++;
		ile[b]++;
		V[a].push_back(b);
		V[b].push_back(a);
	}
	vector<int> del;
	for(int i=1;i<=n;i++) {
		if(ile[i]<d){
			del.push_back(i);
			D(dout << "D:" << i << "\n");
		}
	}
	while(!del.empty()) {
		int i = del.back();
		del.pop_back();
		if(G[i] == 0) {
			G[i]=-1;
			D(dout << "pop:" << i << "\n");
			for(vector<int>::iterator it = V[i].begin(); it != V[i].end(); it++) {
				int x = *it;
				if(G[x]==0) {
					ile[x]--;
					D(dout << "prcs:" << x << " : " << ile[x] << "\n");
					if(ile[x]<d) del.push_back(x);
				}
			}
		}
	}

	D(
		for(int i=1;i<=n;i++) {
			dout << "G[" << i <<"]:" << G[i] << "\n";
		}
	)
	int mx=0,midx=1;
	for(int i=1;i<=n;i++) {
		int Gile=0;
		if(G[i] == 0) {
			vector<int> stack;
			stack.push_back(i);
			while(!stack.empty()) {
				int x=stack.back();
				stack.pop_back();
				if(G[x] == 0) {
					G[x] = i;
					Gile++;
					stack.insert(stack.end(), V[x].begin(), V[x].end());
				}
			}
			if(mx < Gile) {
				mx = Gile;
				midx = i;
			}
		}
	}

	int idx=0;
	for(int i=1;i<=n;i++) {
		if(G[i] == midx) ile[idx++]=i;
	}
	sort(ile,ile+idx);
	if(idx+1<d) {
		printf("NIE");
	} else {
		printf("%d\n",idx);
		for(int i=0;i<idx;i++) {
			printf("%d ", ile[i]);
		}
	}
	return 0;
}