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
#include <iostream>
#include <list>
#include <vector>
using namespace std;

struct city {
	vector < int > edges;
	int power;
	bool addedToQue;
	int color;
};

city cc [200001];
int n, m, d, a, b;
list < int> que;

void addToQue(int x){
	if(cc[x].addedToQue==false){
		cc[x].addedToQue = true;
		que.push_back(x);
	}
}

void executeQue(){
	while(!que.empty()){
		int z = que.front();
		que.pop_front();
		for(unsigned i = 0;i<cc[z].edges.size();++i){
			if(--cc[cc[z].edges[i]].power<d){
				addToQue(cc[z].edges[i]);
			}
		}
	}
}

int curBest = 0;
int color = -1;
void startSizeCalculation(int x, int c){
	int size = 0;
	cc[x].power = 0;
	addToQue(x);
	while(!que.empty()){

		int z = que.front();
		cc[z].color = c;
		que.pop_front();
		++size;

		for(unsigned i = 0;i<cc[z].edges.size();++i){
			if(cc[cc[z].edges[i]].power>=d){
				addToQue(cc[z].edges[i]);
			}
		}

	}
	if(size>curBest){
		curBest = size;
		color = c;
	}

}

int main () {
	ios_base::sync_with_stdio(0);
	cin >> n >> m >> d;
	for(int i = 0;i<n;++i){
		cc[i].power=0;
		cc[i].addedToQue=false;
		cc[i].color = 0;
	}
	for(int i = 0;i<m;++i){
		cin >> a >> b;
		--a;--b;
		cc[a].edges.push_back(b);
		cc[b].edges.push_back(a);
		cc[a].power++;
		cc[b].power++;
	}

	for(int i = 0; i<n;++i){
		if(cc[i].power<d)
			addToQue(i);
	}

	executeQue();

	for(int i = 0;i<n;++i){
		cc[i].addedToQue = false;
	}

	int paint = 1;
	for(int i = 0;i<n;++i){
		if(cc[i].power>=d && cc[i].addedToQue==false){
			startSizeCalculation(i, paint++);
		}
	}
	if(curBest == 0){
		cout << "NIE\n";
	}
	else{
		cout << curBest << "\n";
		for(int i = 0;i<n;++i){
			if(cc[i].color == color){
				cout << i + 1 << " ";
			}
		}
	}

	return 0;
}