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

static const int MAX_N = 200009;

int N, M, D;
std::vector<int> graph[MAX_N];
int deg[MAX_N];
int queue[MAX_N];
int q_front, q_end;
bool in_queue[MAX_N];


int FU[MAX_N];
int FUsize[MAX_N];
int FUfind(int x) {
	if (FU[x] == x)
		return x;
	return FU[x] = FUfind(FU[x]);
}
void FUunion(int x, int y) {
	int a = FUfind(x);
	int b = FUfind(y);
	if (a != b) {
		FUsize[a] += FUsize[b];
		FU[b] = a;
	}
}


int main() {
	scanf("%d%d%d", &N, &M, &D);
	
	for (int i = 0; i < M; ++i) {
		int a, b;
		scanf("%d%d", &a, &b);
		graph[a].push_back(b);
		graph[b].push_back(a);
		deg[a]++;
		deg[b]++;
	}
	
	for (int i = 1; i <= N; ++i) {
		if (deg[i] < D) {
			in_queue[i] = true;
			queue[q_front++] = i;
		}	
	}
	
	while (q_front != q_end) {
		int current = queue[q_end++];
		for (int i = 0; i < graph[current].size(); ++i) {
			int next = graph[current][i];
			deg[next]--;

			if (deg[next] < D && (!in_queue[next])) {
				in_queue[next] = true;
				queue[q_front++] = next;
			}		
		}
	}
	
	for (int i = 1; i <= N; ++i) {
		FU[i] = i;
		FUsize[i] = 1;
	}
	
	for (int i = 1; i <= N; ++i) {
		if (!in_queue[i])
			for (int j = 0; j < graph[i].size(); ++j) {
				if (!in_queue[graph[i][j]]) {
					FUunion(i, graph[i][j]);
				}
		}
	}
	
	int max = 0;
	int max_i = 0;
	for (int i = 1; i <= N; ++i) {
		int a = FUfind(i);
		int s = FUsize[a];
		if (s > max) {
			max = s;
			max_i = a;
		}
	}
	
	if (max < D) {
		printf("NIE\n");
	} else {
		printf("%d\n", max);
		for (int i = 1; i <= N; ++i) {
			int a = FUfind(i);
			if (a == max_i)
				printf("%d ", i);
		}
		printf("\n");
	}
	
	
	return 0;
}