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
96
97
#include <stdint.h>
#include <iostream>
#include <vector>
#include <queue>

const int32_t MAX = 200001;

struct {
	std::vector<int32_t> edges;
	bool inQueue{false};
	int32_t color{0};
	int32_t size{0};
} G[MAX];

int32_t a, b, k, m, n;
std::queue<int32_t> Q;

int32_t dfs(int32_t begin, int32_t sccID) {
	G[begin].color = sccID;
	int32_t size = 1;
	
	for(auto &v : G[begin].edges) {
		if(!G[v].color && !G[v].inQueue)
			size += dfs(v, sccID);
	}

	return size;
}

void run(void) {
	std::cin >> n >> m >> k;

	for(int32_t i = 0; i < m; ++i) {
		std::cin >> a >> b;

		G[a-1].edges.push_back(b-1);
		G[b-1].edges.push_back(a-1);
	}

	for(int32_t i = 0; i < n; ++i) {
		G[i].size = G[i].edges.size();
		if(G[i].edges.size() < k) {
			G[i].inQueue = true;
			Q.push(i);
		}
	}

	while(!Q.empty()) {
		int32_t current = Q.front();
		Q.pop();

		int32_t tmp = 0;
		for(auto &v : G[current].edges) {
			G[v].size --;
			
			if(G[v].inQueue)
				continue;

			if(G[v].size < k) {
				G[v].inQueue = true;
				Q.push(v);
			}
		}
	}

	int32_t maxValue, maxID, tmp;
	maxValue = maxID = -1;

	for(int32_t i = 0; i < n; ++i) {
		if(!G[i].color && !G[i].inQueue) {
			tmp = dfs(i, i+1);
			if(tmp > maxValue) {
				maxValue = tmp;
				maxID = i+1;
			}
		}
	}

	if(maxValue == -1) {
		std::cout << "NIE" << std::endl;
		return;
	}

	std::cout << tmp << std::endl;
	for(int32_t i = 0; i < n; ++i) {
		if(G[i].color == maxID)
			std::cout << i+1 << " ";
	}
	std::cout << std::endl;
}

int main(void) {
	std::ios_base::sync_with_stdio(false);
	run();

	return 0;
}