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

using namespace std;

set<int> edges[200009];

struct vert{
	int n;
	int neigh;
};

bool operator<(vert a, vert b){
	if(a.neigh!=b.neigh){
		return a.neigh<b.neigh;
	}
	return a.n<b.n;
}

int main(){
	int n,m,d;
	scanf("%d %d %d",&n,&m,&d);
	for(int i=0;i<m;i++){
		int a,b;
		scanf("%d %d",&a,&b);
		a--;b--;
		edges[a].insert(b);
		edges[b].insert(a);
	}
	set<vert> vertices;
	for(int i=0;i<n;i++){
		vert v;
		v.n=i;
		v.neigh=edges[i].size();
		vertices.insert(v);
	}
	while(!vertices.empty()){
		vert v=*(vertices.begin());
		if(v.neigh>=d){break;}
		vertices.erase(vertices.begin());
		for(auto it=edges[v.n].begin();it!=edges[v.n].end();it++){
			vert oth;
			oth.n=*it;
			oth.neigh=edges[*it].size();
			auto it2=vertices.find(oth);
			vertices.erase(*it2);
			oth.neigh--;
			vertices.insert(oth);
			edges[*it].erase(v.n);
		}
	}
	set<int> largest;
	while(!vertices.empty()){
		set<int> cur;
		vert start=*(vertices.begin());
		cur.insert(start.n);
		vertices.erase(vertices.begin());
		queue<vert> q;
		q.push(start);
		while(!q.empty()){
			vert v=q.front();
			q.pop();
			for(auto it=edges[v.n].begin();it!=edges[v.n].end();it++){
				vert u;
				u.n=*it;
				u.neigh=edges[*it].size();
				if(vertices.count(u)){
					vertices.erase(vertices.find(u));
					q.push(u);
					cur.insert(u.n);
				}
			}
		}
		if(cur.size()>largest.size()){
			largest=cur;
		}
	}
	if(largest.size()==0){
		printf("NIE\n");
	}
	else{
		printf("%d\n",largest.size());
		for(auto it=largest.begin();it!=largest.end();it++){
			printf("%d ",1+*it);
		}
		printf("\n");
	}
}