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
#include <cstdio>
#include <list>
using namespace std;

list<int>* graph;
int n,m,d,from,to;
int* edges;
int* visited;
list<int> biggest;

void remove_not_communicated(int vertex) {
	if(edges[vertex] < d) {
		edges[vertex] = 0;
		for (list<int>::iterator it = graph[vertex].begin(); it != graph[vertex].end(); it++) {
			int n_vertex = *it;
			graph[n_vertex].remove(vertex);
			edges[n_vertex]--;
			remove_not_communicated(n_vertex);
		}
		graph[vertex].clear();
	}
}

void dfs(int v, list<int> &route) {
//	printf("%d -> %d\n", v, route.size());
	if (!visited[v]) {
		visited[v] = true;
		if (edges[v] > 0) {
			route.push_front(v);
			for (list<int>::iterator it = graph[v].begin(); it != graph[v].end(); it++) {
				dfs(*it, route);
			}
		}
	}
}

int main() {
	scanf("%d %d %d", &n, &m, &d);
	
	graph = new list<int>[n+1];
	edges = new int[n+1];

	for(int i=0;i<=n;i++) edges[i] = 0;
	
	for (int i=0;i<m;i++) {
		scanf("%d %d", &from, &to);
		graph[from].push_front(to);
		graph[to].push_front(from);
		edges[from]++;
		edges[to]++;
	}

	for(int i=1;i<=n;i++) {
		remove_not_communicated(i);
	}
	
//	for(int i=1;i<=n;i++) {
//		printf("edges[%d] = %d\n", i, edges[i]);
//	}
	
	visited = new int[n+1];
	for (int i=0;i<=n;i++) visited[i] = 0;
	
	list<int> tmpList;
	for (int i=1;i<=n;i++) {
		dfs(i, tmpList);
//		printf("After %d vertex tmpList size is %d\n", i, tmpList.size());
		if(tmpList.size() > biggest.size()) {
			biggest = tmpList;
		}
		tmpList.clear();
	}
	
	if(biggest.size() > 0) {
		printf("%lu\n", biggest.size());
		biggest.sort();
		for(list<int>::iterator it = biggest.begin(); it != biggest.end(); it++) {
			printf("%d ", *it);
		}
		printf("\n");
	} else {
		printf("NIE\n");
	}
	
	return 0;
}