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

using namespace std;

vector<int> tab[200001], graf;

int n, m, d, i, p, k, x, y, ans;
bool met[200001], killed[200001];
int cons[200001], kolejka[200001];

void dfs( int w )
{
	met[w] = 1;
	graf.push_back( w );
	i++;
	for( int a = 0; a < tab[w].size(); a++ )
	{
		if( !killed[ tab[w][a] ] && !met[ tab[w][a] ] )dfs( tab[w][a] );
	}
}
void bfs( int w )
{
	for( int a = 0 ; a < tab[w].size(); a++ )
	{
		cons[ tab[w][a] ]--;
		if( cons[ tab[w][a] ] < d && !killed[ tab[w][a] ] )
		{
			killed[ tab[w][a] ] = 1;
			kolejka[++p] = tab[w][a];
		}
	}
	while( k < p )bfs( kolejka[ ++k ] ); 
}
int main()
{
	ios_base::sync_with_stdio( 0 );
	cin>>n>>m>>d;
	for( int a = 1; a <= m; a++ )
	{
		cin>>x>>y;
		tab[x].push_back( y );
		tab[y].push_back( x );
		cons[x]++;
		cons[y]++;
	}
	for( int a = 1; a <= n; a++ )
	{
		if( cons[a] < d )
		{
			killed[a] = 1;
			met[a] = 1;
			kolejka[++p] = a;
		}
	}
	while( k < p )
	{
		bfs( kolejka[ ++k ] );
	}
	for( int a = 1; a <= n; a++ )met[a] = 0;
	for( int a = 1; a <= n; a++ )
	{
		if( !met[a] && !killed[a] )dfs( a );
		ans = max( ans, i );
		i = 0;
	}
	for( int a = 1; a <= n; a++ )met[a] = 0;
	graf.clear();
	for( int a = 1; a <= n; a++ )
	{
		if( !met[a] && !killed[a] )dfs( a );
		if( i == ans )
		{
			if( ans )
			{
				cout<<ans<<endl;
				sort( graf.begin(), graf.end() );
				for( int b = 0; b < graf.size(); b++ )cout<<graf[b]<<" ";
			}
			else cout<<"NIE";
			break;
		}
		graf.clear();
		i = 0;
	}
	return 0;
}