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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include <cstdlib>
#include <stdio.h>
#include <iostream>

#include <vector>
#include <set>
#include <map>
#include <queue>
#include <algorithm>

typedef std::vector<unsigned> Component;

struct Node {
    Node() : Traversed(false),Active(true) {}
	std::set<unsigned> Neighbour;

    bool Traversed;
	bool Active;
	int Neighbours();
};

int Node::Neighbours()
{
	return Neighbour.size();
}

static void FindConnectedNodes(std::vector<Node>& graph, unsigned node_id, Component& component) 
{
    Node& node = graph[node_id];
    if (!node.Traversed) {

        node.Traversed = true;
        component.push_back(node_id);

		for (auto i = node.Neighbour.begin(); i != node.Neighbour.end(); ++i)
		{
			if (graph[*i].Active)
				FindConnectedNodes(graph, *i, component);
		}
    }
}

std::vector<Component> FindGraphComponents(std::vector<Node>& graph) 
{
    std::vector<Component> components;
    for (unsigned node_id = 1; node_id < graph.size(); ++node_id) {
		if (!graph[node_id].Traversed && graph[node_id].Active) {
            components.push_back(Component());
            FindConnectedNodes(graph, node_id, components.back());
        }
    }
    return components;
}

int main()
{
	std::ios_base::sync_with_stdio(0);
	unsigned node_count, edge_count, d;
    std::cin >> node_count >> edge_count >> d;
	std::vector<Node> graph(node_count+1); 

	for (unsigned i = 0; i < edge_count; ++i) 
	{
        unsigned from, to;
        std::cin >> from >> to;
		graph[from].Neighbour.insert(to);
        graph[to].Neighbour.insert(from);
    }

	std::queue<int> kolejka;
	for (unsigned node_id = 1; node_id < graph.size(); ++node_id) //3
	{
		if (graph[node_id].Active && graph[node_id].Neighbours()<d) //4
		{
			graph[node_id].Active  = false; //5
			kolejka.push(node_id); //6

			while(!kolejka.empty()) //7
			{
				unsigned w = kolejka.front();//8
				kolejka.pop();
			//	for(unsigned neigh_id=0;neigh_id < graph[w].Neighbour.size();neigh_id++) //iteruje po sasiadach w
				for (auto neighit = graph[w].Neighbour.begin();neighit!=graph[w].Neighbour.end();++neighit)
				{
					unsigned id_sasiada = *neighit;
					graph[id_sasiada].Neighbour.erase(w);

					if (graph[id_sasiada].Active && graph[id_sasiada].Neighbours()<d)
					{
						graph[id_sasiada].Active  = false; //5
						kolejka.push(id_sasiada); //6
					}
				}
			}
		}
	}

    auto components = FindGraphComponents(graph);
    std::sort(components.begin(),components.end(),[] (const Component& a, const Component& b) { return a.size() > b.size(); });


	if (components.size()>0)
	{
		auto components_i = components.begin();
		std::cout << (*components_i).size() << std::endl;

		std::sort((*components_i).begin(),(*components_i).end());
		for (auto edge_i = components_i->begin(); edge_i != components_i->end(); ++edge_i)
            std::cout << *edge_i << ' ';
	}
	else
	{
		std::cout << "NIE" << std::endl;
	}
	return 0;
}