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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <set>
#include <vector>

using namespace std;

#define MAXN 200001
set<int> E[MAXN];
int rootOf[MAXN];
vector<int> group[MAXN];

struct CmpCities
{
	bool operator () (int c1, int c2) const
	{
		auto c1ESize = E[c1].size();
		auto c2ESize = E[c2].size();
		return c1ESize == c2ESize
			? c1 < c2
			: c1ESize < c2ESize;
	}
};

int main()
{
	int n, m;
	auto d = 0u;
	scanf("%d%d%u", &n, &m, &d);
	for(int i = 0; i < m; ++i)
	{
		int a, b;
		scanf("%d%d", &a, &b);
		E[a].insert(b);
		E[b].insert(a);
	}
	
	set<int, CmpCities> cities;
	for(int i = 1; i <= n; ++i)
		cities.insert(i);
		
	
	decltype(cities.begin()) toRem;
	int toRemI;
	while(!cities.empty() && 
		E[toRemI = *(toRem = cities.begin())].size() < d)
	{
		cities.erase(toRem);
		while(!E[toRemI].empty())
		{
			auto first = E[toRemI].begin();
			auto adjCityI = *first;
			E[toRemI].erase(first);
			
			cities.erase(adjCityI);
			E[adjCityI].erase(toRemI);
			cities.insert(adjCityI);
		}
	}
	
	vector<int> roots;
	while(!cities.empty())
	{
		auto root = *cities.begin();
		if(rootOf[root] == 0)
		{
			roots.push_back(root);	
			rootOf[root] = root;	
			auto& Q = group[root];
			Q.push_back(root);
			auto i = 0u;
			while(i < Q.size())
			{
				auto city = Q[i++];
				cities.erase(cities.find(city));
				for(auto adj : E[city])
					if(rootOf[adj] == 0)
					{
						rootOf[adj] = root;
						Q.push_back(adj);
					}
			}
		}
	}
	
	if(roots.empty())
	{
		puts("NIE");
	}
	else
	{
		auto resultRoot = 0;
		for(auto root : roots)
			if(group[root].size() > group[resultRoot].size())
				resultRoot = root;
		auto& resultGroup = group[resultRoot];
		sort(resultGroup.begin(), resultGroup.end());
		printf("%u\n", resultGroup.size());
		for(auto city : resultGroup)
			printf("%d ", city);
	}
	
	return 0;
}