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

struct Problem
{
  Problem(int n, int d) : n_(n), d_(d), adj_(n), removed_(n), visited_(n) {}
  
  void addEdge(int u, int v) { adj_[u].push_back(v); adj_[v].push_back(u); }
  void dfs(int v, vector<int>& cc);
  vector<int> solve();
  
  int n_,d_;
  vector<vector<int>> adj_;
  vector<bool> removed_, visited_;
};

void Problem::dfs(int v, vector<int>& cc)
{
  visited_[v] = true;
  cc.push_back(v);
  for (int u : adj_[v])
    if (!removed_[u] && !visited_[u]) dfs(u,cc);
}

vector<int> Problem::solve()
{
  vector<int> deg(n_);
  for (int i=0; i<n_; ++i) deg[i] = (int)adj_[i].size();
  queue<int> q;
  for (int i=0; i<n_; ++i)
    if (deg[i] < d_)
    {
      removed_[i] = true;
      q.push(i);
    }
  while (!q.empty())
  {
    int v = q.front();
    q.pop();
    for (int u : adj_[v])
    {
      --deg[u];
      if (deg[u] < d_ && !removed_[u])
      {
        removed_[u] = true;
        q.push(u);
      }
    }
  }
  vector<int> result;
  for (int i=0; i<n_; ++i)
  {
    if (removed_[i] || visited_[i]) continue;
    vector<int> cc;
    dfs(i,cc);
    if (cc.size() > result.size()) result = move(cc);
  }
  sort(result.begin(),result.end());
  return result;
}

int main()
{
  int n,m,d;
  scanf("%d%d%d", &n, &m, &d);
  Problem p(n,d);
  for (int i=0; i<m; ++i)
  {
    int u,v;
    scanf("%d%d", &u, &v);
    p.addEdge(u-1,v-1);
  }
  vector<int> result = p.solve();
  if (result.empty()) printf("NIE\n");
  else
  {
    printf("%d\n", (int)result.size());
    for (int x : result) printf("%d ", x+1);
    printf("\n");
  }
}