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
#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
#include<stack>
#include<algorithm>
//#include<utility>
using namespace std;

int n, m, d, odw[200010], sasiedzi[200010], wynik1, wynik2, twynik1[200010], twynik2[200010], a, b;
bool wynik=true, bylo=false;
queue<int> DFS;
queue<int> sprawdz;
queue<int> eee;
vector<int> graf[200010];
//*************************************************************************
int main()
{
	scanf("%d%d%d", &n , &m, &d);
	//printf("e");
	for(int i=0; i<m; i++)
	{
		scanf("%d%d", &a, &b);
		graf[a].push_back(b);
		graf[b].push_back(a);
		sasiedzi[a]++;
		sasiedzi[b]++;
		if(sasiedzi[a]>=d) sprawdz.push(a);
		if(sasiedzi[b]>=d) sprawdz.push(b);
	}
	for(int i=0; i<n; i++)
	{
		if(graf[i].size()<d)
		{
			for(int j=0; j<graf[i].size(); j++)
			{
				sasiedzi[graf[i][j]]--;
				if(sasiedzi[graf[i][j]]<d) DFS.push(graf[i][j]);
				//else sprawdz.push(graf[i][j]);
			}
			odw[i]=1;
		}
	}
	//cout<<"wyszlo\n";
	while(!DFS.empty())
	{
		for(int i=0; i<graf[DFS.front()].size(); i++)
		{
			if(odw[graf[DFS.front()][i]]!=1)
			{
				sasiedzi[graf[DFS.front()][i]]--;
				if(sasiedzi[graf[DFS.front()][i]]<d) DFS.push(graf[DFS.front()][i]);
				//else sprawdz.push(graf[DFS.front()][i]]);
			}
		}
		odw[DFS.front()]=1;
		DFS.pop();
	}
	//cout<<"wyszlo\n";
	while(!sprawdz.empty())
	{
		//cout<<sprawdz.top()<<endl;
		a=sprawdz.front();
		//sprawdz.pop();
		//odw[a]=1;
		if(sasiedzi[a]>=d&&odw[a]!=1)
		{
			eee.push(a);
			while(!eee.empty())
			{
				b=eee.front();
				//eee.pop();
				if(sasiedzi[b]>=d&&odw[b]!=1)
				{
				if(wynik==true)
				{
					twynik1[wynik1]=b;
					wynik1++;
				}
				else if(wynik==false)
				{
					twynik2[wynik2]=b;
					wynik2++;
				}
				for(int i=0; i<graf[b].size(); i++)
				{
					if(sasiedzi[graf[b][i]]>=d&&odw[graf[b][i]]!=1)
					{
						//bylo=true;
						/*if(wynik==true)
						{
							twynik1[wynik1]=graf[a][i];
							wynik1++;
						}
						else
						{
							twynik2[wynik2]=graf[a][i];
							wynik2++;
						}*/
						eee.push(graf[b][i]);
						//odw[graf[a][i]]=1;
					}
				}
				//cout<<wynik1<<" "<<wynik2<<endl;
				/*if(bylo==false)
				{
					if(wynik1>=wynik2)
					{
						wynik=false;
						wynik2=0;
					}
					else
					{
						wynik=true;
						wynik1=0;
					}
				}
				bylo=true;*/
				}
				odw[b]=1;
				eee.pop();
			}
			if(wynik1>=wynik2)
			{
				wynik=false;
				wynik2=0;
			}
			else
			{
				wynik=true;
				wynik1=0;
			}
		}
		odw[a]=1;
		sprawdz.pop();
	}
	//cout<<"wyszlo\n";
	if(wynik1>=wynik2&&wynik1>1)
	{
		printf("%d\n", wynik1);
		sort(twynik1, twynik1+wynik1);
		for(int i=0; i<wynik1; i++) printf("%d ", twynik1[i]);
	}
	else if(wynik2>1)
	{
		printf("%d\n", wynik2);
		sort(twynik2, twynik2+wynik2);
		for(int i=0; i<wynik2; i++) printf("%d ", twynik2[i]);
	}
	else printf("NIE");
	printf("\n");
	return 0;
}