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
#include <bits/stdc++.h>

using namespace std;

enum State {
  UNVISITED = 0,
  VISITED = 1,
  DELETED = 2,
};

const int MAXN = 200009;

int n, d, visitedCount, result, resultRepresentative;
State state[MAXN];
int degree[MAXN];
vector<int> neighbours[MAXN];

void readData() {
  ios_base::sync_with_stdio(false);
  int m, a, b;
  cin >> n >> m >> d;
  while (m--) {
    cin >> a >> b;
    degree[a]++;
    degree[b]++;
    neighbours[a].push_back(b);
    neighbours[b].push_back(a);
  }
}

void deleteSmall() {
  queue<int> small;
  for (int i = 1; i <= n; i++) {
    if (degree[i] < d) {
      small.push(i);
    }
  }
  while (!small.empty()) {
    int element = small.front();
    small.pop();
    if (state[element] != DELETED) {
      state[element] = DELETED;
      for (int neighbour : neighbours[element]) {
        degree[neighbour]--;
        if (degree[neighbour] < d) {
          small.push(neighbour);
        }
      }
    }
  }
}

void dfs(int v) {
  visitedCount++;
  state[v] = VISITED;
  for (int neighbour : neighbours[v]) {
    if (state[neighbour] == UNVISITED) {
      dfs(neighbour);
    }
  }
}

int main() {
  readData();
  deleteSmall();
  for (int i = 1; i <= n; i++) {
    int oldVisitedCount = visitedCount;
    if (state[i] == UNVISITED) {
      dfs(i);
    }
    if (visitedCount - oldVisitedCount > result) {
      result = visitedCount - oldVisitedCount;
      resultRepresentative = i;
    }
  }
  if (result > 0) {
    vector<int> solution;
    for (int i = 1; i <= n; i++) {
      if (state[i] != DELETED) {
        state[i] = UNVISITED;
      }
    }
    dfs(resultRepresentative);
    for (int i = 1; i <= n; i++) {
      if (state[i] == VISITED) {
        solution.push_back(i);
      }
    }
    sort(solution.begin(), solution.end());
    cout << result << endl;
    for (int element : solution) {
      cout << element << " ";
    }
    cout << endl;
  } else {
    cout << "NIE" << endl;
  }
}