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

const int INF = 1000 * 1000;
const int MAXN = 200 * 1000;
const int MAXM = 200 * 1000;

std::vector<int> neighbours[MAXN + 5];
int nodeDegree[MAXN + 5];
bool isUseless[MAXN + 5];
bool done[MAXN + 5];
bool doneSecond[MAXN + 5];
int subgraphId[MAXN + 5];
int subgraphSize[MAXN + 5];

int main() {
	int n, m, d;
	scanf("%d%d%d", &n, &m, &d);
	int a, b;
	for (int i = 0; i < m; i++) {
		scanf("%d%d", &a, &b);
		neighbours[a].push_back(b);
		neighbours[b].push_back(a);
	}

	std::queue<int> bfsQueue;
	for (int i = 1; i <= n; i++) {
		nodeDegree[i] = neighbours[i].size();
		if (nodeDegree[i] < d) {
			bfsQueue.push(i);
			isUseless[i] = true;
		}
	}

	int current;
	while (!bfsQueue.empty()) {
		current = bfsQueue.front();
		bfsQueue.pop();
		done[current] = true;

		for (int i = 0; i < neighbours[current].size(); i++) {
			if (!done[neighbours[current][i]]) {
				nodeDegree[neighbours[current][i]]--;
			}

			if (!isUseless[neighbours[current][i]] && nodeDegree[neighbours[current][i]] < d) {
				bfsQueue.push(neighbours[current][i]);
				isUseless[bfsQueue.back()] = true;
			}
		}
	}

	int currentSubId = 1;
	for (int i = 1; i <= n; i++) {
		if (isUseless[i] == false && subgraphId[i] == 0) {
			bfsQueue.push(i);
			doneSecond[i] = true;
			while (!bfsQueue.empty()) {
				current = bfsQueue.front();
				subgraphId[current] = currentSubId;
				subgraphSize[currentSubId]++;
				bfsQueue.pop();
				for (int i = 0; i < neighbours[current].size(); i++) {
					if (!isUseless[neighbours[current][i]] && !doneSecond[neighbours[current][i]]) {
						bfsQueue.push(neighbours[current][i]);
						doneSecond[neighbours[current][i]] = true;
					}
				}
			}
			currentSubId++;
		}
	}

	int result = -1;
	int resultSubId = 0;
	for (int i = 1; i <= n; i++) {
		if (subgraphSize[i] >= d + 1 && subgraphSize[i] > result) {
			result = subgraphSize[i];
			resultSubId = i;
		}
	}

	if (result == -1) {
		printf("NIE");
	} else {
		printf("%d\n", result);
		for (int i = 1; i <= n; i++) {
			if (subgraphId[i] == resultSubId) {
				printf("%d ", i);
			}
		}
	}

	return 0;
}