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

//containers:
#include <vector>
#include <list>
#include <queue>

#include <numeric>
#include <algorithm>

using namespace std;

const int MAX = 2e5 + 1;
vector <int> Graph[MAX];

void deleteVertice(int d)
{
	for(vector<int>::iterator it = Graph[d].begin(); it != Graph[d].end(); it++)
	{
		sort(Graph[*it].begin(), Graph[*it].end());
		vector<int>::iterator bs = lower_bound<vector<int>::iterator, int>
			(Graph[*it].begin(), Graph[*it].end(), d);
		Graph[*it].erase(bs);
	}
	Graph[d].clear();
}

int main(int argc, char** argv) {
	ios_base::sync_with_stdio(false);
	int n, m, d;
	
	cin >> n >> m >> d;

	//----------graph construction: ----------
	for(int i = 1; i <= m; i++)
	{
		int a, b;
		
		cin >> a >> b;
		Graph[a].push_back(b);
		Graph[b].push_back(a);
	}

	//---------deleting vertices of degrees < d: ---------
	int *tempTemp = new int[n];
	iota <int*, int> (tempTemp, tempTemp + n, 1);
	list <int> allLeft(tempTemp, tempTemp + n);
	list<int>::iterator lt = allLeft.begin();

	bool deletedSomeVertex = true;
	while(deletedSomeVertex)
	{
		queue <list<int>::iterator> QTemp;
		deletedSomeVertex = false;
		for(lt = allLeft.begin(); lt != allLeft.end(); lt++)
		{
			if(Graph[*lt].size() < unsigned(d))
			{
				deleteVertice(*lt); 
				QTemp.push(lt);
				deletedSomeVertex = true;
			}
		} 
		while(!QTemp.empty())
		{
			allLeft.erase(QTemp.front());
			QTemp.pop();
		}
	}

	//---------determinig number of d-connected subgraphs and comparison of its module: --------
	//list <vector<int>> vertexLeft_Part;
	//bool *checked = new bool[n];
	//for(int i = 0; i < n; i++) checked[i] = false;
	//for(lt = allLeft.begin(); lt != allLeft.end(); lt++)
	//{
	//	if(checked[*lt])
	//		continue;
	//	//BFS
	//	enum VertexProperty{covered, discovered, explored};
	//	VertexProperty *graphVertexProperty = new VertexProperty[n];
	//	queue <int> Q;
	//	vector<int> Part;
	//	Part.push_back(*lt); checked(*lt) = true;
	//	graphVertexProperty[*lt] = explored;


	//}
	int als = allLeft.size();
	if(als)
		cout << als << endl;
	else
		cout << "NIE" << endl;
	for(list<int>::iterator it = allLeft.begin(); it != allLeft.end(); it++)
		cout << *it << ' ';
	cout << endl;

	return 0;
}