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
//	Michał Wiatrowski

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);

	int n, m, d;
	cin >> n >> m >> d;

	vector<vector<int>> graph(n);
	vector<int> roads(n, 0);

	vector<bool> marked(n, true);

	queue<int> q;

	for (int i = 0; i < m; ++i) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		graph[a].push_back(b);
		graph[b].push_back(a);
		roads[a] += 1;
		roads[b] += 1;
	}

	for (int i = 0; i < n; ++i) {
		if (roads[i] < d) {
			q.push(i);
			marked[i] = false;
		}
	}

	while (!q.empty()) {
		int active = q.front();
		q.pop();

		for (int i : graph[active]) if (marked[i]) {
			roads[i] -= 1;
			if (roads[i] < d) {
				marked[i] = false;
				q.push(i);
			}
		}
	}

	vector<int> largestComponent;

	int city = 0;
	while (city < n) {
		if (marked[city]) {
			q.push(city);
			marked[city] = false;

			vector<int> component;

			while (!q.empty()) {
				int active = q.front();
				q.pop();

				component.push_back(active);

				for (int i : graph[active]) if (marked[i]) {
					marked[i] = false;
					q.push(i);
				}
			}

			if (component.size() > largestComponent.size()) {
				largestComponent = component;

			}
		} else {
			city++;
		}
	}

	if (largestComponent.size() == 0) {
		cout << "NIE" << endl;
	} else {
		cout << largestComponent.size() << endl;

		for (int i : largestComponent)
			marked[i] = true;
		
		for (int i = 0; i < n; ++i) if (marked[i])
			cout << i + 1 << ' ';
		cout << endl;
	}

	return 0;
}