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

int main()
{
	int n, m, d, a, b;
	std::cin >> n >> m >> d;
	
	std::vector<std::vector<int>> graph(n + 1);
	std::vector<int> deg(n + 1, 0);
	for (int i = 0; i < m; ++i) {
		std::cin >> a >> b;
		graph[a].emplace_back(b);
		graph[b].emplace_back(a);
		++deg[a]; ++deg[b];
	}

	auto comp = [&](int _v1, int _v2) { return deg[_v1] == deg[_v2] ? _v1 < _v2 : deg[_v1] < deg[_v2]; };
	std::set<int, decltype(comp)> s(comp);
	for (int i = 0; i < n; ++i) {
		s.insert(i + 1);
	}

	std::vector<bool> removed(n + 1, false);
	while (!s.empty() && deg[*s.begin()] < d) {
		auto top = *s.begin();
		s.erase(s.begin());
		if (!removed[top]) {
			for (auto &it : graph[top]) {
				if (!removed[it]) {
					s.erase(it);
					--deg[it];
					s.insert(it);
				}
			}
			removed[top] = true;
		}
	}

	if (s.empty()) {
		std::cout << "NIE" << std::endl;
	} else {
		std::vector<int> sol1(s.size()), sol2(s.size());
		std::vector<int> *best = &sol1, *local = &sol2;
		int b_end = 0, l_end = 0;

		while (!s.empty()) {
			if (!removed[*s.begin()]) {
				removed[*s.begin()] = true;
				std::queue<int> q;
				q.push(*s.begin());
				while (!q.empty()) {
					auto top = q.front();
					q.pop();
					(*local)[l_end++] = top;
					for (auto &it : graph[top]) {
						if (!removed[it]) {
							q.push(it);
							removed[it] = true;
						}
					}
				}
				if (l_end > b_end) {
					std::swap(best, local);
					std::swap(b_end, l_end);
				}
				l_end = 0;
			}
			s.erase(s.begin());
		}

		std::sort(best->begin(), best->begin() + b_end);
		std::cout << b_end << std::endl;
		for (int i = 0; i < b_end; ++i) {
			std::cout << (*best)[i] << " ";
		}
	}
	
	return 0;
}