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
#include <algorithm>
#include <cstdint>
#include <iostream>
#include <stack>
#include <utility>
#include <vector>

int main()
{
	std::uint_fast32_t n, m, d;
	std::cin >> n >> m >> d;

	std::vector<std::vector<decltype(n)>> edges(n);

	for (decltype(m) i = 0; i < m; ++i)
	{
		decltype(n) city_1, city_2;
		std::cin >> city_1 >> city_2;
		--city_1;
		--city_2;

		edges[city_1].push_back(city_2);
		edges[city_2].push_back(city_1);
	}

	for (auto& vertices : edges)
		std::sort(vertices.begin(), vertices.end());


	for (decltype(n) i = 0; i < n; ++i)
	{
		if (edges[i].size() < d)
		{
			std::stack<decltype(n)> stack;
			stack.push(i);

			while (!stack.empty())
			{
				auto top = stack.top();
				stack.pop();

				for (auto other_city : edges[top])
				{
					auto it = std::lower_bound(edges[other_city].begin(), edges[other_city].end(), top);
					edges[other_city].erase(it);
					if (edges[other_city].size() < d)
						stack.push(other_city);
				}
				edges[top].clear();
			}
		}
	}


	const decltype(n) UNVISITED = n, PENDING = n + 1;

	std::vector<decltype(n)> group_indexes(n, UNVISITED);
	decltype(n) best_group_index = UNVISITED;
	decltype(n) best_group_size = 1;

	for (decltype(n) i = 0; i < n; ++i)
	{
		if (group_indexes[i] == UNVISITED)
		{
			decltype(n) group_size = 0;
			std::stack<decltype(n)> stack;
			stack.push(i);

			while (!stack.empty())
			{
				auto top = stack.top();
				stack.pop();

				group_indexes[top] = i;
				++group_size;

				for (auto other_city : edges[top])
				{
					if (group_indexes[other_city] == UNVISITED)
					{
						stack.push(other_city);
						group_indexes[other_city] = PENDING;
					}
				}
			}

			if (group_size > best_group_size)
			{
				best_group_size = group_size;
				best_group_index = i;
			}
		}
	}

	if (best_group_index < n)
	{
		std::cout << best_group_size << std::endl;
		std::cout << (best_group_index + 1);
		for (decltype(n) i = best_group_index + 1; i < n; ++i)
		{
			if (group_indexes[i] == best_group_index)
				std::cout << ' ' << (i + 1);
		}
		std::cout << std::endl;
	}
	else
		std::cout << "NIE";
}