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 <cstdio>
#include <vector>
#include <queue>
using namespace std;
struct wp{
	vector<int> v;
};
wp t[200005];
wp t2[200005];
int zlicz[200005];
queue<int> q;
int odw[200005];
int licz[200005];
pair<int,int> pol[200005];
bool odww[200005];
int main(){
	int n,m,d;
	scanf("%d%d%d", &n,&m,&d);
	for (int i = 0; i < m; i++){
		int a,b;
		scanf("%d%d", &a,&b);
		t[a].v.push_back(b);
		t[b].v.push_back(a);
		pol[i] = make_pair(a,b);
	}
	for (int i = 1; i <= n; i++){
		zlicz[i] = t[i].v.size();
		if (zlicz[i] < d){
			q.push(i);
//			zlicz[i] = 0;
			odww[i] = 1;
	//		printf("%d ", i);
		}
		//printf("%d ", zlicz[i]);
	}
	while(!q.empty()){
		int v1 = q.front();
		q.pop();
		zlicz[v1] = 0;
		for(vector<int>::iterator it = t[v1].v.begin(); it != t[v1].v.end(); it++){
			if (odww[*it] == 0){
				zlicz[*it]--;
				if (zlicz[*it] < d){
					odww[*it] = 1;
				//	zlicz[*it] = 0;
					q.push(*it);
					//printf("%d\n", *it);
				}
			}
		}
	}
	for (int i = 0; i < m; i++){
		int a = pol[i].first;
		int b = pol[i].second;
		if (zlicz[a] >= d && zlicz[b] >= d){
			t2[a].v.push_back(b);
			t2[b].v.push_back(a);
		}
	}
/*	for (int i = 1; i <= n; i++){
		printf("%d: ", i);
		for (vector<int>::iterator it = t2[i].v.begin(); it != t2[i].v.end(); it++)
			printf("%d ", *it);
		printf("\n");
	}*/
	for (int i = 1; i <= n; i++)
		odw[i] = -1;
	for (int i = 1; i <= n; i++){
		if(zlicz[i] >= d && odw[i] == -1){
			odw[i] = i;
			q.push(i);
			while(!q.empty()){
				int v1 = q.front();
				q.pop();
				for (vector<int>::iterator it = t2[v1].v.begin(); it != t2[v1].v.end(); it++){
					if (odw[*it] == -1){
						odw[*it] = i;
						q.push(*it);
					}
				}
			}
		}
	}
	for (int i = 1; i <= n; i++){
		//printf("%d ", odw[i]);
		if (odw[i] != -1)
			licz[odw[i]]++;
	}
	int besti = 0;
	int maks = 0;
	for (int i = 1; i <= n; i++){
		//printf("%d ", licz[odw[i]]);
		if (maks < licz[i]){
			maks = licz[i];
			besti = i;
		}
	}
	//printf("%d %d\n", maks,besti);
	if (maks < d){
		printf("NIE");
		return 0;
	}
	printf("%d\n", maks);
	for (int i = 1; i <= n; i++){
		if (odw[i] == besti)
			printf("%d ", i);
	}
}