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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#ifndef DEBUG_MODE
#define NDEBUG
#endif

#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <cstdio>

#include <cassert>
#include <set>

using namespace std;

struct Node {
	Node() : degree(0), marker(-1), is_removed(false), will_be_checked(false) {}

	vector<int> neighbours;
	int degree, marker;
	bool is_removed, will_be_checked;
};

struct Graph {
	Graph(int num_nodes) { nodes.resize(num_nodes); }

	void addEdge(int a, int b) {
		nodes[a].neighbours.push_back(b);
		nodes[b].neighbours.push_back(a);
		nodes[a].degree++;
		nodes[b].degree++;
	}

	void removeNode(int id) {
		Node &node = nodes[id];
		node.is_removed = true;
		for(int n = 0; n < (int)node.neighbours.size(); n++) {
			int nid = node.neighbours[n];
			nodes[nid].degree--;
		}
	}

	int markReachable(int start, int value) {
		vector<int> list;
		list.push_back(start);
		int count = 0;

		while(!list.empty()) {
			int id = list.back();
			list.pop_back();

			Node &node = nodes[id];
			if(node.marker != -1)
				continue;
			node.marker = value;
			count++;

			for(int n = 0; n < (int)node.neighbours.size(); n++) {
				int nid = node.neighbours[n];
				if(!nodes[nid].is_removed && nodes[nid].marker == -1)
					list.emplace_back(nid);
			}
		}

		return count;
	}

	Node &operator[](int n) { return nodes[n]; }

	vector<Node> nodes;
};

int main() {
	ios_base::sync_with_stdio(false);
	int nodes_count, edges_count, min_degree;
	cin >> nodes_count >> edges_count >> min_degree;

	Graph graph(nodes_count);
	for(int n = 0; n < edges_count; n++) {
		int a, b;
		cin >> a >> b;
		graph.addEdge(a - 1, b - 1);
	}

	vector<int> check_nodes;
	for(int n = 0; n < nodes_count; n++)
		if(graph[n].degree < min_degree) {
			check_nodes.push_back(n);
			graph[n].will_be_checked = true;
		}

	while(!check_nodes.empty()) {
		int node_id = check_nodes.back();
		Node &node = graph[node_id];
		check_nodes.pop_back();

		node.will_be_checked = false;
		if(node.degree < min_degree) {
			graph.removeNode(node_id);
			for(int n = 0; n < (int)node.neighbours.size(); n++) {
				Node &neighbour = graph[node.neighbours[n]];
				if(neighbour.degree < min_degree && !neighbour.will_be_checked &&
				   !neighbour.is_removed) {
					neighbour.will_be_checked = true;
					check_nodes.push_back(node.neighbours[n]);
				}
			}
		}
	}

	int max_count = 0;
	int max_marker = 0;

	for(int n = 0; n < nodes_count; n++)
		if(!graph[n].is_removed) {
			int marker = n;
			int count = graph.markReachable(n, marker);
			if(count > max_count) {
				max_count = count;
				max_marker = marker;
			}
		}

	if(max_count > 0) {
		cout << max_count << endl;
		for(int n = 0; n < nodes_count; n++)
			if(graph[n].marker == max_marker)
				cout << (n + 1) << ' ';
		cout << endl;
	} else { cout << "NIE" << endl; }

	return 0;
}