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

struct Node{
	int color;
	int nRoads;
	set<int> roads;
	
	Node() : nRoads(0), color(0) {}
};

int n, m, d;
Node *nodes;


void remove(int num){
	if(nodes[num].color < 0) return;
	
	nodes[num].color = -1;
	nodes[num].nRoads = 0;
	
	for(set<int>::iterator it = nodes[num].roads.begin(); it != nodes[num].roads.end(); it++){
		nodes[*it].nRoads--;
		nodes[*it].roads.erase(num);
		
		if(nodes[*it].nRoads < d)
			remove(*it);
	}
	
	nodes[num].roads.clear();
}

int paint(int num, int col){
	if(nodes[num].color != 0) return 0;
	
	nodes[num].color = col;
	int painted = 1;
	
	for(set<int>::iterator it = nodes[num].roads.begin(); it != nodes[num].roads.end(); it++)
		painted += paint(*it, col);
	
	return painted;
}

int main(){
	scanf("%d %d %d", &n, &m, &d);
	
	nodes = new Node[n+1];
	
	for(int i=1; i<=n; i++){
		nodes[i].nRoads = 0;
		nodes[i].color = 0;
	}
	
	for(int i=1; i<=m; i++){
		int a, b;
		scanf("%d %d", &a, &b);
		
		nodes[a].roads.insert(b);
		nodes[b].roads.insert(a);
		nodes[a].nRoads++;
		nodes[b].nRoads++;
	}
	
	for(int i=1; i<=n; i++)
		if(nodes[i].nRoads < d)
			remove(i);
	
	int bestColor = 0;
	int bestColored = 0;
	
	for(int i=1; i<=n; i++){
		int colored = paint(i, i);
		
		if(colored > bestColored){
			bestColored = colored;
			bestColor = i;
		}
	}
	
	if(bestColored > 0){
		printf("%d\n", bestColored);
		
		for(int i=1; i<=n; i++)
			if(nodes[i].color == bestColor)
				printf("%d ", i);
	}else{
		printf("NIE\n");
	}
	
	delete [] nodes;
	return 0;
}