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
#include<cstdio>
#include<queue>
#include<vector>

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)

#define VERTICES 200000

using namespace std;

vector<int> graph[VERTICES];
int deg[VERTICES];
bool pushed[VERTICES];
bool color[VERTICES];
int id[VERTICES];
queue<int> Q;

int DFS(int v, int const& d, int const& ass_id) {
  int size = 1;
  color[v] = false;
  id[v] = ass_id;
  for (int neighbour : graph[v]) {
    if (color[neighbour] && (deg[neighbour] >= d)) {
      size += DFS(neighbour, d, ass_id);
    }
  }
  return size;
}

int main() {
  int n, m, d, a, b;
  scanf("%d%d%d", &n, &m, &d);
  while (m--) {
    scanf("%d%d", &a, &b);
    --a;
    --b;
    graph[a].push_back(b);
    graph[b].push_back(a);
  }
  for (int i = 0; i < n; ++i) {
    deg[i] = graph[i].size();
    pushed[i] = false;
    if (deg[i] < d) {
      Q.push(i);
      pushed[i] = true;
    }
  }
  while (!Q.empty()) {
    int element = Q.front();
    Q.pop();
    for (int neighbour : graph[element]) {
      deg[neighbour]--;
      if ((deg[neighbour] < d) && !pushed[neighbour]) {
        Q.push(neighbour);
        pushed[neighbour] = true;
      }
    }
  }
  REP(i, n) {
    color[i] = true;
    id[i] = -1;
  }
  int id_cnt = 0;
  int max_size = 0, iid = -1;
  REP(i, n) {
    if (color[i] && (deg[i] >= d)) {
      int size = DFS(i, d, id_cnt);
      if (size > max_size) {
        max_size = size;
        iid = id_cnt;
      }
      id_cnt++;
    }
  }
  if (iid == -1) {
    printf("NIE\n");
  } else {
    printf("%d\n", max_size);
    REP(i, n) {
      if (id[i] == iid) {
        printf("%d ", i + 1);
      }
    }
    printf("\n");
  }
  return 0;
}