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

using namespace std;

int main() {
	
	int n, m;
	unsigned int d;
	cin >> n >> m >> d;
	
	vector< vector<int> > r(n+1);
	for (int i=0; i<m; i++) {
		int a, b;
		cin >> a >> b;
		r[a].push_back(b);
		r[b].push_back(a);
	}
	
	vector<unsigned int> c(n+1);
	vector<int> t;
	vector<bool> removed(n+1);
	for (int i=1; i<=n; i++) {
		if ( r[i].size() < d ) {
			// cerr << i << " ";
			t.push_back(i);
		}
		c[i] = r[i].size();
	}
	// cerr << ""; for (int i=1; i<=n; i++) cerr << i << ':' << c[i] << " "; cerr << endl;
	
	for ( vector<int>::size_type tidx = 0; tidx < t.size(); tidx++ ) {
		int cur = t[tidx];
		// cerr << cur << endl;
		
		for ( unsigned int i=0; i<r[cur].size(); i++ ) {
			int del = r[cur][i];
			if ( !removed[del] ) {
				c[del]--;
				if ( c[del]==d-1 ) {
					t.push_back(del);
				}
			}
		}
		c[cur] = 0;
		removed[cur] = true;
		
		// cerr << ""; for (int i=1; i<=n; i++) cerr << i << ':' << c[i] << " "; cerr << endl;
	}
	
	vector<int> best, cur;
	for ( int i=1; i<=n; i++ ) {
		if ( !removed[i] ) {
			cur = vector<int>();
			removed[i] = true;
			cur.push_back(i);
			// cerr << "t" << i << ' ';
			for ( unsigned int curidx=0; curidx<cur.size(); curidx++ ) {
				for ( unsigned int j=0; j<r[cur[curidx]].size(); j++ ) {
					int push = r[cur[curidx]][j];
					if ( !removed[push] ) {
						removed[push] = true;
						cur.push_back(push);
						// cerr << "t" << push << ' ';
					}
				}
			}
			if ( cur.size()>best.size() ) {
				best = cur;
				// cerr << "best" << best.size() << endl;
			}
		}
	}
	if ( best.size()==0 ) {
		cout << "NIE\n";
	} else {
		cout << best.size() << "\n";
		sort( best.begin(), best.end() );
		for ( unsigned int i=0; i<best.size(); i++ ) {
			cout << best[i] << ' ';
		}
		cout << "\n";
	}

	return 0;
}