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

using namespace std;

typedef set<int> Vertex;
typedef vector<Vertex> Graph;


struct DegComparator {
  Graph const &G;
  
  DegComparator(Graph const &G): G(G) { };
  ~DegComparator() { }
  
  bool operator()(int const &a, int const &b) const {
    if(G[a].size() != G[b].size()) return G[a].size() < G[b].size();
    return a < b;
  }
};


int dfs(Graph const &G, vector<int> &component, int const &u, int const &cid) {
  int ret = 1;
  component[u] = cid;
  
  for(set<int>::iterator it = G[u].begin(); it != G[u].end(); ++it) {
    if(component[*it]) continue;
    ret += dfs(G, component, *it, cid);
  }
  
  return ret;
}


int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  
  int n, m, d;
  cin >> n >> m >> d;
  
  Graph G(n);
  
  for(int i = 0; i < m; ++i) {
    int a, b;
    cin >> a >> b; --a; --b;
    
    G[a].insert(b);
    G[b].insert(a);
  }
  
  DegComparator dc(G);
  set<int, DegComparator> H(dc);
  for(int i = 0; i < n; ++i) H.insert(i);
  
  int top;
  while(not H.empty() and int(G[top = *H.begin()].size()) < d) {
    H.erase(top);
    
    vector<int> moved;
    for(set<int>::iterator it = G[top].begin(); it != G[top].end(); ++it) {
      H.erase(*it);
      G[*it].erase(top);
      H.insert(*it);
    }
    
    G[top].clear();
  }
  
  if(not H.empty()) {
    vector<int> component(n, 0);
    int cid = 1;
    int bestCid = 0;
    int bestLen = -1;
    
    for(set<int, DegComparator>::iterator it = H.begin(); it != H.end(); ++it) {
      if(component[*it]) continue;
      int len = dfs(G, component, *it, cid);
      if(len > bestLen) {  bestLen = len; bestCid = cid; }
      ++cid;
    }
    
    cout << bestLen << '\n';
    for(int i = 0; i < n; ++i) {
      if(component[i] == bestCid) cout << i+1 << ' ';
    }
    cout << '\n';
  } else {
    cout << "NIE\n";
  }
  
  return 0;
}