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
93
94
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>

using namespace std;

const int MAX_N=200005;
const int MAX_M=200005;

vector <int> V[MAX_N];
vector <int> wynik;
bool odw[MAX_N];
void DFS(int v){
	wynik.push_back(v);
	odw[v]=true;
	for(int i=0; i<V[v].size(); ++i){
		if(!odw[V[v][i]])DFS(V[v][i]);
	}
}

bool czyZly[MAX_N];
int licznik;
queue <int> Q;
int Vsize[MAX_N];
int n,m,d,a,b;
int maxi,ID;

void Licz(int v){
	++licznik;
	czyZly[v]=true;
	for(int i=0; i<V[v].size(); ++i){
		if(!czyZly[V[v][i]])Licz(V[v][i]);
	}
}

void BFS(){
	while(!Q.empty()){
		int v=Q.front();
		Q.pop();
		for(int i=0; i<V[v].size(); ++i){
			int vi=V[v][i];
			if(!czyZly[vi]){
				--Vsize[vi];
				if(Vsize[vi]<d){
					czyZly[vi]=true;
					odw[vi]=true;
					Q.push(vi);
				}
			}
		}
	}
}

int main(){
	ios_base::sync_with_stdio(0);
	cin>>n>>m>>d;
	for(int i=0; i<m; ++i){
		cin>>a>>b;
		V[a].push_back(b);
		V[b].push_back(a);
		++Vsize[a];
		++Vsize[b];
	}
	for(int i=1; i<=n; ++i){
		if(Vsize[i]<d){
			Q.push(i);
			odw[i]=true;
			czyZly[i]=true;
		}
	}
	BFS();
	for(int i=1; i<=n; ++i){
		if(!czyZly[i]){
			licznik=0;
			Licz(i);
			if(licznik>maxi){
				maxi=licznik;
				ID=i;
			}
		}
	}
	DFS(ID);
	if(maxi>0){
		cout<<maxi<<endl;
		sort(wynik.begin(), wynik.end());
		for(int i=0; i<wynik.size(); ++i){
			cout<<wynik[i]<<" ";
		}
		cout<<endl;
	}
	else cout<<"NIE"<<endl;
	return 0;
}