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

using std::begin;
using std::end;

class vertex {
  public:
   static std::vector<int32_t> actual;
   bool visited = false;
   std::set<int32_t> neighbour;
   void befriend(const int32_t);
   void separate(const int32_t);
   size_t size();
   void dfs();
 }*graph;

std::vector<int32_t> vertex::actual;

class cmp {
  public:
   bool operator()(vertex* a, vertex* b) {
     if(a->size() == b->size()) {
       return a < b;
      }
     return a->size() < b->size();
    }
 };

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(NULL);
  uint32_t n, m, d;
  std::cin >> n >> m >> d;
  graph =  new vertex[n];
  for(uint32_t a, b, i = 0; i < m; ++i) {
    std::cin >> a >> b;
    graph[a-1].befriend(b-1);
    graph[b-1].befriend(a-1);
   }
  std::set<vertex*, cmp> sorted;
  for(auto ptr = graph; ptr < graph+n; ++ptr) {
    sorted.insert(ptr);
   }
  while(sorted.size() > 1 && (**sorted.begin()).size() < d) {
    const auto erased = *sorted.begin();
    sorted.erase(*sorted.begin());
    for(const auto& old_friend : erased->neighbour) {
      sorted.erase(&graph[old_friend]);
      graph[old_friend].separate(std::distance(graph,erased));
      sorted.insert(&graph[old_friend]);
     }
   }
  std::vector<int32_t> answer;
  for(auto x : sorted) {
    if(x->visited == false)
     x->dfs();
    if(vertex::actual.size() > answer.size()) {
      std::swap(vertex::actual, answer);
     }
    vertex::actual.clear();
   }
  if(answer.size() < 2) {
    std::cout << "NIE\n";
    return 0;
   }
  std::sort(begin(answer), end(answer));
  std::cout << answer.size() << '\n';
  std::copy(begin(answer), end(answer),
            std::ostream_iterator<int32_t>(std::cout, " "));
  std::cout << '\n';
 }

void vertex::befriend(const int32_t x) {
  neighbour.insert(x);
 }

void vertex::separate(const int32_t x) {
  neighbour.erase(x);
 }

size_t vertex::size() {
  return neighbour.size();
 }

void vertex::dfs() {
  actual.push_back(1 + this - graph);
  visited = true;
  for(const auto& x : neighbour)
   if(graph[x].visited == false) {
     graph[x].dfs();
    }
 }