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
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include <algorithm>
#include <cstdio>
#include <stack>
#include <vector>

using namespace std;

class FindUnion {
 public:
  FindUnion(const int n) : parent_(n, -1) {}

  int Find(int i) {
    int j = i;
    while (parent_[j] >= 0) j = parent_[j];
    while (parent_[i] >= 0) {
      int k = parent_[i];
      parent_[i] = j;
      i = k;
    }
    return j;
  }

  int Size(int i) {
    i = Find(i);
    return -parent_[i];
  }

  void Union(int i, int j) {
    i = Find(i);
    j = Find(j);
    if (i == j) return;
    if (parent_[i] < parent_[j]) {
      parent_[i] += parent_[j];
      parent_[j] = i;
    } else {
      parent_[j] += parent_[i];
      parent_[i] = j;
    }
  }

 private:
  vector<int> parent_;
};

stack<int> s;
vector<bool> deleted;

void Enqueue(const int i) {
  if (deleted[i]) return;
  deleted[i] = true;
  s.push(i);
}

int main() {
  int n;
  int m;
  int d;
  scanf("%d%d%d", &n, &m, &d);
  deleted.resize(n, false);
  vector<int> degree(n, 0);
  vector<pair<int, int> > edges;
  while (m--) {
    int a;
    int b;
    scanf("%d%d", &a, &b);
    ++degree[--a];
    ++degree[--b];
    edges.push_back(make_pair(a, b));
    edges.push_back(make_pair(b, a));
  }
  sort(edges.begin(), edges.end());

  vector<int> offsets;
  {
    int i = 0;
    while (i < edges.size()) {
      while (edges[i].first >= offsets.size()) offsets.push_back(i);
      ++i;
    }
    while (offsets.size() <= n) offsets.push_back(i);
  }

  for (int i = 0; i < n; ++i) if (degree[i] < d) Enqueue(i);

  while (!s.empty()) {
    const int i = s.top();
    s.pop();
    for (int j = offsets[i]; j < offsets[i + 1]; ++j)
      if (--degree[edges[j].second] < d) Enqueue(edges[j].second);
  }

  FindUnion f(n);
  for (int i = 0; i < n; ++i) if (!deleted[i]) {
    for (int j = offsets[i]; j < offsets[i + 1]; ++j)
      if (!deleted[edges[j].second]) f.Union(i, edges[j].second);
  }

  int best = -1;
  for (int i = 0; i < n; ++i) if (!deleted[i])
    if (best == -1 || f.Size(i) > f.Size(best)) best = i;

  if (best == -1) {
    printf("NIE\n");
  } else {
    printf("%d\n%d", f.Size(best), best + 1);
    for (int i = 0; i < n; ++i) if (i != best) if (f.Find(i) == f.Find(best))
      printf(" %d", i + 1);
    printf("\n");
  }

  return 0;
}