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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include <cstdio>
#include <set>
#include <list>
#include <queue>
#include <algorithm>

//#define DEBUG

#ifdef DEBUG
#define D(x) x
#else
#define D(x)
#endif

using namespace std;

struct City {
  set<int> neighbours;
  int degree;
  int marker;
  bool processed;
};

const int MAX_CITIES = 200005;
City cities[MAX_CITIES];
int sorted[MAX_CITIES];

void print_set(const set<int>& l) {
    set<int>::const_iterator it = l.begin();
    while(it != l.end()) {
      printf("%d ", *it);
      it++;
    }
}

void print_cities(const int n) {
  for(int i = 1; i <= n; i++) {
    printf("City #%d (%d/%d): ", i, cities[i].degree, cities[i].marker);
    print_set(cities[i].neighbours);
    printf("\n");
  }
}

bool cmp_by_degree(const int x, const int y) {
  return cities[x].degree < cities[y].degree;
}

int mark(int city, int marker, int d) {
  if(cities[city].marker == 0 && cities[city].degree >= d) {
    cities[city].marker = marker;
    set<int>::const_iterator it = cities[city].neighbours.begin();
    int sum = 1;
    while(it != cities[city].neighbours.end()) {
      sum += mark(*it, marker, d);
      it++;
    }
    return sum;
  }
  return 0;
}

int main() {
  int n, m, d;
  scanf("%d %d %d", &n, &m, &d);

  for(int i = 1; i <= n; i++) {
    cities[i] = (City){set<int>(), 0, 0, false};
  }

  for(int j = 1; j <= m; j++) {
    int a, b;
    scanf("%d %d", &a, &b);
    cities[a].neighbours.insert(b);
    cities[b].neighbours.insert(a);
    cities[a].degree++;
    cities[b].degree++;
  }

  D(print_cities(n);)

  queue<int> q;

  for(int i = 1; i <= n; i++) {
    q.push(i);
  }

  while(!q.empty()) {
    int i = q.front();
    q.pop();
    if(cities[i].degree < d) {
      cities[i].degree = 0;
      set<int>::const_iterator it = cities[i].neighbours.begin();
      while(it != cities[i].neighbours.end()) {
        cities[*it].degree--;
        if(cities[*it].processed && cities[*it].degree + 1 == d) q.push(*it);
        it++;
      }
    }
    cities[i].processed = true;
  }

  D(printf("----\n");)
  D(print_cities(n);)

  int marker = 1;
  int best_marker = 0;
  int best_qty = 0;
  for(int i = 1; i <= n; i++) {
    if(cities[i].marker == 0 && cities[i].degree >= d) {
      list<int> current;
      int marked = mark(i, marker, d);
      D(printf("Marked %d with marker %d.\n", marked, marker);)
      if(marked > best_qty) {
        best_marker = marker;
        best_qty = marked;
      }
      marker++;
    }
  }
  
  D(printf("----\n");)
  D(print_cities(n);)

  D(printf("Result: %d (marker %d)\n", best_qty, best_marker);)

  if(best_qty > 0) {
    printf("%d\n", best_qty);
    for(int i = 1; i <= n; i++) {
      if(cities[i].marker == best_marker) {
        printf("%d ", i);
      }
    }
    printf("\n");
  } else {
    printf("NIE\n");
  }

  return 0;
}