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

#define MAXN 200001

using namespace std;

typedef pair<int,int> PII;

bool wierzcholekUsuniety[MAXN], vis[MAXN];
int n,m,d;
int stopienWierzcholka[MAXN];
vector<int> v[MAXN], spojnaSkladowa[MAXN];
priority_queue<PII> q;

void dfs (int x, int y){
	vis[x] = true;
	spojnaSkladowa[y].push_back(x); //dorzucamy wierzcholek do aktualnej spojnej skladowej
	for (int i=0; i<v[x].size(); ++i){
		if (!vis[v[x][i]] && !wierzcholekUsuniety[v[x][i]]){
			dfs(v[x][i], y);
		}
	}
	return;
}

int main(){
	scanf("%d%d%d", &n, &m, &d);
	
	for (int i=0; i<m; ++i){
		int x,y;
		scanf("%d%d", &x, &y);
		v[x].push_back(y);
		v[y].push_back(x);
	}	
	
	for(int i=1; i<=n; ++i){
		stopienWierzcholka[i] = v[i].size();
		wierzcholekUsuniety[i] = false;
		q.push(PII(-stopienWierzcholka[i], i));
	}
	
	//ODCHUDDZENIE GRAFU
	while (!q.empty()){
		PII gora = q.top();
		q.pop();
		int stopien = -gora.first;
		int wierzcholekA = gora.second;
			
		if (stopien < d && !wierzcholekUsuniety[wierzcholekA]){ //trzeba usunac ten wierzcholek z grafu (i juz nigdy do niego nie wchodzic)
			wierzcholekUsuniety[wierzcholekA] = true;
			for (int i=0; i<v[wierzcholekA].size(); ++i){
				int wierzcholekB = v[wierzcholekA][i];
				if (!wierzcholekUsuniety[wierzcholekB]){	//wszak nie moge wejsc do wierzcholka, ktory zostal juz usuniety!!
					--stopienWierzcholka[wierzcholekB];
					q.push(PII(-stopienWierzcholka[wierzcholekB], wierzcholekB));
				}
			}
		}
		//nie ma sensu juz przegladac wierzcholkow, wszystkie beda mialy stopien wiekszy niz 'd'
	}
		
	//ZNALEZNIENIE WSPOLNYCH SKLADOWYCH
	int nrSkladowej = 0;
	for (int i=1; i<=n; ++i){
		if (!vis[i] && !wierzcholekUsuniety[i]){
			++nrSkladowej;
			dfs(i, nrSkladowej);
		}
	}
	
	//ZNALEZNIENIE NAJWIEKSZEJ WSPOLNEJ SKLADOWEJ
	int nrNajwiekszejSkladowej = 1;
	for (int i=1; i<=nrSkladowej; ++i){
		if (spojnaSkladowa[nrNajwiekszejSkladowej].size() < spojnaSkladowa[i].size()){
			nrNajwiekszejSkladowej = i;
		}
	}
	
	if (spojnaSkladowa[nrNajwiekszejSkladowej].size()){
		printf("%d\n", spojnaSkladowa[nrNajwiekszejSkladowej].size());
		sort(spojnaSkladowa[nrNajwiekszejSkladowej].begin(), spojnaSkladowa[nrNajwiekszejSkladowej].end());
		for (int i=0; i<spojnaSkladowa[nrNajwiekszejSkladowej].size(); ++i){
			printf("%d ", spojnaSkladowa[nrNajwiekszejSkladowej][i]);
		}
	}
	else{
		printf("NIE");
	}
	printf("\n");
	
	return 0;
}