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

typedef vector<int> CC;

int n, m, d, a, b;
int ranks[200001];
bool deleted[200001];
vector<int> edges[200001];
queue<int> deletionQ;
CC bestCC;

void DFS(int v, CC& cc){
	cc.push_back(v);
	deleted[v] = true;
	for(int i = 0; i < edges[v].size(); ++i){
		int neigh = edges[v][i];
		if(!deleted[neigh]){
			DFS(neigh, cc);
		}
	}
}

void getCC(int v){
	CC newCC;
	DFS(v, newCC);
	if(newCC.size() > bestCC.size()){
		bestCC = newCC;
	}
}


int main(){
	scanf("%d %d %d", &n, &m, &d);
	
	for(int i = 1; i <= n; ++i){
		ranks[i] = 0;
		deleted[i] = false;
	}
	
	for(int i = 0; i < m; ++i){
		scanf("%d %d", &a, &b);
		edges[a].push_back(b);
		edges[b].push_back(a);
		++ranks[a];
		++ranks[b];
	}
	
	for(int i = 1; i <= n; ++i){
		if(ranks[i] < d){
			deletionQ.push(i);
			deleted[i] = true;
		}
	}
	
	while(!deletionQ.empty()){
		int v = deletionQ.front();
		deletionQ.pop();
		for(int i = 0; i < edges[v].size(); ++i){
			int neigh = edges[v][i];
			--ranks[neigh];
			if(ranks[neigh] < d && !deleted[neigh]){
				deletionQ.push(neigh);
				deleted[neigh] = true;
			}
		}
	}
	
	// we can use Deleted as Visited now tbh
	
	for(int i = 1; i <= n; ++i){
		if(!deleted[i]){
			getCC(i);
		}
	}
	
	if(bestCC.empty()){
		printf("NIE\n");
		return 0;
	}
	
	sort(bestCC.begin(), bestCC.end());
	printf("%d\n", bestCC.size());
	for(int i = 0; i < bestCC.size(); ++i){
		printf("%d ", bestCC[i]);
	}
	
	return 0;
}