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

namespace {
  void dfs(int v, vector<vector<int>> const& neigh, vector<bool>& visited, vector<int>& component)
  {
    visited[v] = true;
    component.push_back(v);
    for (auto const& w: neigh[v]) {
      if (visited[w]) continue;
      dfs(w, neigh, visited, component);
    }
  }

  vector<int> solve(vector<vector<int>> const& neigh, int d)
  {
    int n = neigh.size();
    vector<int> degree(n);
    vector<int> todo;
    vector<bool> marked(n);
    for (int i = 0; i < n; ++i) {
      degree[i] = neigh[i].size();
      if (degree[i] < d) {
        todo.push_back(i);
        marked[i] = true;
      }
    }
    while (!todo.empty()) {
      auto v = todo.back();
      todo.pop_back();
      for (auto const& w: neigh[v]) {
        --degree[w];
        if (!marked[w] && degree[w] < d) {
          todo.push_back(w);
          marked[w] = true;
        }
      }
    }
    vector<int> res;
    for (int i = 0; i < n; ++i) {
      if (marked[i]) continue;
      vector<int> cur;
      dfs(i, neigh, marked, cur);
      if (cur.size() > res.size()) {
        res = move(cur);
      }
    }
    return res;
  }
}

int main()
{
  iostream::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, m, d;
  cin >> n >> m >> d;
  
  vector<vector<int>> neigh(n);
  for (int i = 0; i < m; ++i) {
    int a, b;
    cin >> a >> b;
    neigh[a-1].push_back(b-1);
    neigh[b-1].push_back(a-1);
  }

  auto res = solve(neigh, d);
  if (res.empty()) {
    cout << "NIE\n";
  } else {
    sort(res.begin(), res.end());
    cout << res.size() << '\n';
    bool first = true;
    for (auto const& x: res) {
      if (!first) cout << ' ';
      else first = false;
      cout << x + 1;
    }
    cout << '\n';
  }

  return 0;
}