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
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
vector <vector <int> > t;
vector <int> ways;
int d;
int n,m;
vector <int> obs;
int DFS(int start, int obszar)
	{
	obs[start]=obszar;
	int res=1;
	for(int i=0;i<t[start].size();i++)
		{
		if(obs[t[start][i]]<0 && ways[t[start][i]]>0) res+=DFS(t[start][i], obszar);
		}
	return res;
	}
void BFS(int start)
	{
//	cout<< "upa" << endl;
	queue <int> q;
	q.push(start);
	vector <bool> odw;
	odw.resize(n,0);
	int up;
	while(!q.empty())
		{
		up=q.front();
		odw[up]=1;
		q.pop();
		ways[up]=-1; // zapominamy o tym miescie
		for(int i=0;i<t[up].size();i++)
			{
			ways[t[up][i]]--;// jako ze up jest do bani, to trzeba odjac jedno polaczenie
			if(ways[t[up][i]]<d && !odw[t[up][i]]) q.push(t[up][i]);
			// wpychamy do kolejki tylko wtedy, gdy miasto na topie nie moze byc w S
			}
		}
	}
int main()
	{
	ios_base::sync_with_stdio(0);
	cin>> n >> m;
	int a,b;
	cin>> d;
	t.resize(n);
	for(int i=0;i<m;i++)
		{
		cin>> a >> b;
		t[a-1].push_back(b-1);
		t[b-1].push_back(a-1);
		}
	ways.resize(n);
	for(int i=0;i<n;i++)
		{
		ways[i]=t[i].size();
		}
//	for(int i=0;i<n;i++) cout<< ways[i] << " ";
//	cout<< endl;
	for(int i=0;i<n;i++)
		{
		if(ways[i]<d) BFS(i);
		}
//	for(int i=0;i<n;i++) cout<< ways[i] << " ";
//	cout<< endl;
	// wyrzucilismy miasta, ktore maja ponizej d polaczen
	// teraz sprawdzamy spojnosc
	int obszar=1;
	obs.resize(n,-1);
	int max_pow=-1;
	int nr_pow=-1;
	int pow;
	for(int i=0;i<n;i++)
		{
		if(obs[i]<0 && ways[i]>0)
			{
			pow=DFS(i, obszar);
			if(pow>max_pow) 	
				{ 
				max_pow=pow;
				nr_pow=obszar;
				}
			obszar++;
			} 
		}
	//for(int i=0;i<n;i++) cout<< obs[i] << " ";
//	cout<< endl;
	if(max_pow==-1) cout<< "NIE" << endl;
	else
		{
		cout<< max_pow << endl;
		for(int i=0;i<n;i++)
			{
			if(nr_pow==obs[i]) cout<< i+1 << " ";
			}
		}
	cout<< endl;
	}