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
#include <cstdio>
#include <algorithm>
#include <vector>
#define FOR(x, n) for(int x = 0, __n = (n); x < __n; x++)
#define FORI(x, a, n) for(int x = (a), __n = (n); x < __n; x++)
#define FORR(x, n) for(int x = (n)-1; x >= 0; x--)

using namespace std;
#define MAXN 100001

#define var long long

struct node {
  bool rem;
  vector<int> L;
  int total;
  node():rem(false), total(0), root(NULL), weight(1){}
  void addConnection(int p) {
    L.push_back(p);
    total++;
  }
  int reduce() {
    return --total;
  }
  
  node* root;
  int weight;
  node* getRoot() {
    if(root) return root = root->getRoot();
    return this;
  }
  void join(node* o) {
    if(root) {
      getRoot()->join(o);
      return;
    }
    o = o->getRoot();
    if(o == this) return;
    if(o->weight > weight) o->join(this);
    o->root = this;
    weight += o->weight;
  }
  
} t[MAXN];

main() {
  int n,m,d; scanf("%d%d%d", &n, &m, &d);
  FOR(i, m) {
    int a, b; scanf("%d%d", &a, &b);
    a--, b--;
    t[a].addConnection(b);
    t[b].addConnection(a);
  }
  vector<int> S;
  FOR(i,n) {
    if(t[i].total < d) {
      S.push_back(i);
      t[i].rem = true;
    }
  }

  while(!S.empty()){
    int v = S.back();
    S.pop_back();
    FOR(i, t[v].L.size()) {
      int j = t[v].L[i];
      if(t[j].rem) continue;
      
      if(t[j].reduce() < d) {
        t[j].rem = true;
        S.push_back(j);
      }
    }
  }
  FOR(i, n) {
    if(t[i].rem) continue;
    FOR(k, t[i].L.size()) {
      int j = t[i].L[k];
      if(t[j].rem) continue;
      t[i].join(&t[j]);
    }
  }
  
  int res = 0;
  node* best = NULL;
  FOR(i, n) {
    if(!t[i].rem && t[i].weight > res) {
      res = t[i].weight;
      best = &t[i];
    }
  }
  if(res > 0) {
    printf("%d\n", res);
    FOR(i, n) {
      if(t[i].getRoot() == best) {
        printf("%d ", i+1);
      }
    }
    printf("\n");
  } else {
    printf("NIE\n");
  }
}