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
117
118
119
120
121
#include <algorithm>
#include <iostream>
#include <cassert>
#include <cstdint>
#include <limits>
#include <vector>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>

#ifdef MYDEBUG
#define AND_FALSE
#else
#define AND_FALSE && false
#endif

#define CHECK(cond) do \
    if (!(cond) AND_FALSE) { \
      cerr << "CHECK failed in line " << __LINE__ << ": " << #cond << endl; \
      exit(1); \
    } \
  while (false)

using namespace std;

using i64 = int64_t;

struct Graph {
  void AddEdge(int a, int b) {
    AddDirectedEdge(a, b);
    AddDirectedEdge(b, a);
  }

  void AddDirectedEdge(int a, int b) {
    CHECK(a != b);
    unordered_set<int>& neighbours = nodes[a];
    edge_counts.erase({neighbours.size(), a});
    CHECK(neighbours.insert(b).second);
    CHECK(edge_counts.insert({neighbours.size(), a}).second);
  }

  void RemoveNode(int a) {
    unordered_set<int>& neighbours = nodes[a];
    for (int neighbour : neighbours) {
  //     cout << "neighbour=" << neighbour << endl;
      RemoveDirectedEdge(neighbour, a);
    }
    int elements_erased = edge_counts.erase({neighbours.size(), a});
    assert(elements_erased == 1);
    nodes.erase(a);
  }

  void RemoveDirectedEdge(int a, int b) {
    assert(a != b);
    unordered_set<int>& neighbours = nodes[a];
    CHECK(edge_counts.erase({neighbours.size(), a}) == 1);
    CHECK(neighbours.erase(b) == 1);
    CHECK(edge_counts.insert({neighbours.size(), a}).second);
  }

  void WalkComponent(int a, unordered_set<int> *component) {
    component->insert(a);
    for (int b : nodes[a]) {
      if (component->count(b) == 0) {
        WalkComponent(b, component);
      }
    }
  }

  unordered_map<int, unordered_set<int>> nodes;
  set<pair<int, int>> edge_counts;  // (edges, node_id)
};

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  int n, m, d;
  cin >> n >> m >> d;

  Graph g;

  for (int i = 0; i < m; ++i) {
    int a, b;
    cin >> a >> b;
    g.AddEdge(a, b);
  }

  while (g.edge_counts.size() > 0 &&
         g.edge_counts.begin()->first < d) {
    // cout << "Removing node: " << g.edge_counts.begin()->second << endl;
    g.RemoveNode(g.edge_counts.begin()->second);
  }

  if (g.nodes.empty()) {
    cout << "NIE" << endl;
  } else {
    unordered_set<int> visited;
    set<int> biggest_component;
    for (auto node : g.nodes) {
      int a = node.first;
      unordered_set<int> component;
      if (visited.count(a) == 0) {
        g.WalkComponent(a, &component);
      }
      visited.insert(component.begin(), component.end());
      if (component.size() > biggest_component.size()) {
        biggest_component.clear();
        biggest_component.insert(component.begin(), component.end());
      }
    }
    cout << biggest_component.size() << endl;
    string separator = "";
    for (int i : biggest_component) {
      cout << separator << i;
      separator = " ";
    }
    cout << endl;
  }
}