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

class Node
{
	public:
		list<unsigned int> polacz;
		unsigned int stopien;
		unsigned int spojnosc;
		void wywal();
		int przeszukaj(int s);
} mapa[200001];
int n,m,d;

void Node::wywal()
{
	stopien=0;
	for(list<unsigned int>::iterator it=polacz.begin();
			it!=polacz.end();
			it++)
	{
		if( mapa[(*it)].stopien != 0)
		{
			mapa[(*it)].stopien--;
			if(mapa[(*it)].stopien<d)
				mapa[(*it)].wywal();
		}
	}
}

int Node::przeszukaj(int s)
{
	spojnosc=s;
	int ilosc=0;
	for(list<unsigned int>::iterator it=polacz.begin();
			it!=polacz.end();
			it++)
	{
		if(mapa[(*it)].stopien!=0 && mapa[(*it)].spojnosc!=s)
		{
			ilosc+=mapa[(*it)].przeszukaj(s);
		}
	}
	return ilosc+1;


}

int main()
{
	ios_base::sync_with_stdio(0);
	cin>>n>>m>>d;
	for(int i=1;i<=n;i++)
	{
		mapa[i].stopien=0;
		mapa[i].spojnosc=0;
	}
	for(int i=0;i<m;i++)
	{
		unsigned int p,d;
		cin>>p>>d;
		mapa[p].stopien++;
		mapa[p].polacz.push_back(d);
		mapa[d].polacz.push_back(p);
		mapa[d].stopien++;
	}

	for(int i=1;i<=n;i++)
		if(mapa[i].stopien!=0 && mapa[i].stopien<d)
			mapa[i].wywal();

	//teraz szukamy największej składowej spojnej
	int maks=0;
	int lsp=0;
	int spojnosc=1;
	for(int i=1;i<=n;i++)
	{
		if(mapa[i].stopien!=0 && mapa[i].spojnosc==0)
		{
			int k=mapa[i].przeszukaj(spojnosc++);
			if(k>maks)
			{
				maks=k;
				lsp=spojnosc-1;
			}
		}
	}
	if(maks!=0)
	{
		cout<<maks<<"\n";
		for(int i=1;i<=n;i++)
			if(mapa[i].spojnosc==lsp)cout<<i<<" ";
	}
	else
		cout<<"NIE";
	
}