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
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cassert>
using namespace std;

//#define DEBUG
#ifdef DEBUG
#define ASSERT(x) assert(x)
#define DEBPRINT(...) fprintf(stderr, __VA_ARGS__)
#else
#define ASSERT(x)
#define DEBPRINT(...)
#endif

#define MAXN 200007

int N, M, D;
vector<int> E[MAXN];
int En[MAXN];
vector<int> Q;
vector<int> SSC[MAXN];
int SSCn;
int C[MAXN];
int R;

int main() {
	int i, j, ii;
	scanf("%d%d%d", &N, &M, &D);
	R = N;
	for (i = 0; i < M; i++) {
		int a, b;
		scanf("%d%d", &a, &b);
		E[a-1].push_back(b-1);
		E[b-1].push_back(a-1);
	}
	for (i = 0; i < N; i++) {
		En[i] = E[i].size();
		if (En[i] < D) {
			R--;
			Q.push_back(i);
			DEBPRINT("(%d) ", i);
		}
	}
	for (i = 0; i < Q.size(); i++) {
		int k = Q[i];
		for (j = 0; j < E[k].size(); j++) {
			int l = E[k][j];
			if (En[l] >= D) { // l still active.
				En[l]--; // connection from k removed.
				if (En[l] < D) {
					R--;
					Q.push_back(l);
					DEBPRINT("(%d) ", l);
				}
			}
		}
	}
	DEBPRINT("\n");
	
	if (R == 0) {
		printf("NIE\n");
		return 0;
	}
	
	SSCn = 0;
	for (i = 0; i < N; i++) {
		if (En[i] >= D && C[i] == 0) {
			SSC[SSCn].push_back(i);
			C[i] = 1;
			DEBPRINT("[%d] ", i);
			for (j = 0; j < SSC[SSCn].size(); j++) {
				int k = SSC[SSCn][j];
				for (ii = 0; ii < E[k].size(); ii++) {
					int l = E[k][ii];
					if (En[l] >= D && C[l] == 0) {
						SSC[SSCn].push_back(l);
						C[l] = 1;
						DEBPRINT("[%d] ", l);
					}
				}
			}
			SSCn++;
			DEBPRINT("\n");
		}
	}
	
	ASSERT(SSCn > 0);
	if (SSCn == 0) {
		printf("NIE\n");
		return 0;
	}
	
	ii = 0;
	for (i = 1; i < SSCn; i++)
		if (SSC[i].size() > SSC[ii].size())
			ii = i;
	
	sort(SSC[ii].begin(), SSC[ii].end());
	printf("%d\n%d", SSC[ii].size(), SSC[ii][0]+1);
	for (i = 1; i < SSC[ii].size(); i++)
		printf(" %d", SSC[ii][i]+1);
	printf("\n");
	
	return 0;
}