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
 98
 99
100
101
102
103
/* Tomasz [Tommalla] Zakrzewski, Potyczki Algorytmiczne 2015 /
/  Seria 2, Grupa B, Zadanie "Mistrzostwa"					*/
#include <cstdio>
#include <set>
#include <vector>

using namespace std;

const int SIZE = 200020;

class Node {
public:
	Node() : exists{true}, visited{false}, deg{0} {}
	vector<int> edges;
	bool exists, visited;
	int deg;
};

Node nodes[SIZE];
vector<int> tmpRes;

struct cmp {
	inline bool operator()(const int &a, const int &b) {
		if (nodes[a].deg != nodes[b].deg) {
			return nodes[a].deg < nodes[b].deg;
		}
		return a < b;
	}
};

void dfs(const int v) {
	tmpRes.push_back(v + 1);
	for (const int u : nodes[v].edges) {
		if (nodes[u].exists && !nodes[u].visited) {
			nodes[u].visited = true;
			dfs(u);
		}
	}
}

int main() {
	int n, m, d, u, v;
	set<int, cmp> s;
	scanf("%d%d%d", &n, &m, &d);
	while (m--) {
		scanf("%d%d", &u, &v);
		--u;
		--v;
		nodes[u].edges.push_back(v);
		nodes[v].edges.push_back(u);
		nodes[u].deg++;
		nodes[v].deg++;
	}

	for (int i = 0; i < n; ++i) {
		s.insert(i);
	}

	while (!s.empty() && nodes[*s.begin()].deg < d) {
		// Remove the node
		v = *s.begin();
		s.erase(s.begin());

		nodes[v].exists = false;
		for (const int t : nodes[v].edges) {
			auto iter = s.find(t);
			bool readd = false;
			if (iter != s.end()) {
				s.erase(iter);
				readd = true;
			}
			nodes[t].deg--;
			if (readd) {
				s.insert(t);
			}
		}
	}

	vector<int> res;
	for (int i = 0; i < n; ++i) {
		if (nodes[i].exists && !nodes[i].visited) {
			nodes[i].visited = true;
			tmpRes.clear();
			dfs(i);
			if (res.size() < tmpRes.size()) {
				res = tmpRes;
			}
		}
	}

	if (res.empty()) {
		puts("NIE");
		return 0;
	}

	printf("%lu\n", res.size());
	for (const int t : res) {
		printf("%d ", t);
	}
	puts("");
	
	return 0;
}