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

using namespace std;

const int N = 3*1e5;

set < pair <int,int> > S;
set < pair <int,int> >::iterator it;
vector <int> Graf[N];
int Zle[N];
int St[N];
int Odw[N];
int ile,nr;


void Wczytaj(int n,int m){
	int i,v,u;
	for(i=0; i<m; i++){
		scanf("%d%d", &v,&u);
		Graf[v].push_back(u);
		Graf[u].push_back(v);
		St[v]++;
		St[u]++;
	}
}

void StworzZbiorS(int n,int d){
	int i;
	int v,u;
	for(i=1; i<=n; i++){
		S.insert(make_pair(St[i],i));
	}
	while(S.size() > 0 && (*S.begin()).first < d){
		v = (*S.begin()).second;
		Zle[v] = 1;
		S.erase(S.begin());
		for(i=0; i<Graf[v].size(); i++){
			u = Graf[v][i];
			if(Zle[u] == 0){
				it = S.find(make_pair(St[u],u));
				S.erase(it);
				St[u]--;
				S.insert( make_pair(St[u],u) );
			}
		}
	}
	//printf("%d\n", S.size());
}

void DFS(int v){
	int i;
	Odw[v] = nr;
	ile++;
	for(i=0; i<Graf[v].size(); i++){
		if(!Zle[Graf[v][i]] && !Odw[Graf[v][i]]) DFS(Graf[v][i]);
	}
}

int main(){
	int n,m,d;
	int i,najw_spojna,kolor;
	scanf("%d%d%d", &n,&m,&d);
	Wczytaj(n,m);
	StworzZbiorS(n,d);
	najw_spojna = -1;
	nr = 1;
	if(S.size() == 0) printf("NIE\n");
	else{
		for(i=1; i<=n; i++){
			if(!Zle[i] && !Odw[i]){
				ile = 0;
				DFS(i);
				if(ile > najw_spojna){
					najw_spojna = ile;
					kolor = nr;
				}
				nr++;
			}
		}
		printf("%d\n", najw_spojna);
		for(i=1; i<=n; i++){
			if(Odw[i] == kolor) printf("%d ", i);
		}
		printf("\n");
	}
	return 0;
}