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
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
#include <cassert>
#include <cstdio>
#include <cstring>

#include <algorithm>
#include <stack>
#include <vector>

static const int MAX_N = 200 * 1000;
static const int MAX_M = 200 * 1000;

struct vert_t
{
	int outDeg;
	int firstConn;
	bool visited;
};

struct conn_t
{
	int to;
	int next;
	bool valid;
};

namespace
{
	static vert_t verts[MAX_N + 1];
	static conn_t conns[2 * MAX_M];
	static int numConns = 0;

	static int n, m, d;
}

static inline void addConnDir(int from, int to)
{
	conns[numConns].to = to;
	conns[numConns].next = verts[from].firstConn;
	conns[numConns].valid = true;
	verts[from].firstConn = numConns;
	verts[from].outDeg++;
	numConns++;
}

static inline void addConn(int a, int b)
{
	addConnDir(a, b);
	addConnDir(b, a);
}

static inline void cutConn(int id)
{
	int baseID = id & (~1);

	for (int i : { 0, 1 })
	{
		conns[baseID | i].valid = false;
		verts[conns[baseID | i].to].outDeg--;
	}
}

static void readData()
{
	scanf("%d %d %d", &n, &m, &d);

	for (int i = 1; i <= n; i++)
	{
		verts[i].outDeg = 0;
		verts[i].firstConn = -1;
		verts[i].visited = false;
	}

	for (int i = 0; i < m; i++)
	{
		int from, to;
		scanf("%d %d", &from, &to);
		addConn(from, to);
	}
}

static void cutSmallVerts()
{
	std::stack<int> vertsToCut;

	for (int i = 1; i <= n; i++)
	{
		if (verts[i].outDeg < d)
			vertsToCut.push(i);
	}

	// Cut vertices below degree d until there are some left
	while (!vertsToCut.empty())
	{
		int vid = vertsToCut.top();
		vertsToCut.pop();
		vert_t & v = verts[vid];


		for (int i = v.firstConn; i != -1; i = conns[i].next)
		{
			// Check if this connection was already cut
			if (!conns[i].valid)
				continue;

			int vtoid = conns[i].to;
			vert_t & vto = verts[vtoid];

			// If the second vertex's degree becomes low,
			// push it onto the stack
			if (vto.outDeg == d)
				vertsToCut.push(vtoid);

			cutConn(i);
		}

		assert(v.outDeg == 0);
	}
}

template<typename F>
static void dfs(int from, bool visibleFlag, F & f)
{
	std::stack<int> vertsToProcess;
	vertsToProcess.push(from);

	verts[from].visited = visibleFlag;

	while (!vertsToProcess.empty())
	{
		int vid = vertsToProcess.top();
		vertsToProcess.pop();
		vert_t & v = verts[vid];

		// Callback
		f(vid);

		for (int i = v.firstConn; i != -1; i = conns[i].next)
		{
			// Check if this connection was already cut
			if (!conns[i].valid)
				continue;

			int vtoid = conns[i].to;
			vert_t & vto = verts[vtoid];

			if (vto.visited != visibleFlag && vto.outDeg >= d)
			{
				vto.visited = visibleFlag;
				vertsToProcess.push(vtoid);
			}
		}
	}
}

static void findLargestComponent()
{
	int largestSize = 0;
	int largestRepr = 0;

	for (int i = 1; i <= n; i++)
	{
		if (verts[i].visited || verts[i].outDeg < d)
			continue;

		int componentSize = 0;
		auto accumulator = [&](int vid) { componentSize++; };

		dfs(i, true, accumulator);

		if (largestSize < componentSize)
		{
			largestSize = componentSize;
			largestRepr = i;
		}
	}

	if (largestRepr == 0)
		puts("NIE");
	else
	{
		std::vector<int> component;
		component.reserve(largestSize);

		auto retriever = [&](int vid) { component.push_back(vid); };
		dfs(largestRepr, false, retriever);

		std::sort(component.begin(), component.end());

		printf("%d\n", largestSize);
		printf("%d", component[0]);

		for (auto it = component.begin() + 1; it != component.end(); ++it)
			printf(" %d", *it);

		putchar('\n');
	}
}

int main()
{
	readData();
	cutSmallVerts();
	findLargestComponent();

	return 0;
}