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
// Krzysztof Baranski
#include <cstdio>
#include <set>
#include <queue>
#include <vector>
#include <functional>
#include <algorithm>
using namespace std;

void visit(int v, vector<set<int> >& g, vector<bool>& vis, vector<int>& comp) {
  //fprintf(stderr,"  Dodajemy miasto %d do skladowej.\n", v);
  vis[v] = true;
  comp.push_back(v);
  for(set<int>::iterator it = g[v].begin(); it != g[v].end(); ++it)
    if(!vis[*it]) visit(*it, g, vis, comp);
}

int main() {
  int n; // liczba miast
  int m; // liczba drog
  int d; // parametr d
  scanf("%d %d %d", &n, &m, &d);

  vector<set<int> > graph(n+1);
  vector<bool> is_ok(n+1, true);
  while(m--) {
    int a, b;
    scanf("%d %d", &a, &b);
    graph[a].insert(b);
    graph[b].insert(a);
  }

  priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > degrees;
  for(int i=1; i<=n; ++i) degrees.push(make_pair(graph[i].size(), i));

  /*/////////////////////////////////////////////////////////////////////////////
  for(int i=1; i<=n; ++i) {
    fprintf(stderr,"Wierzcholek nr %2d ma stopien %d. Ok? - %s\n", i, graph[i].size(), (is_ok[i] ? "true" : "false"));
  }
  /*/////////////////////////////////////////////////////////////////////////////

  while(degrees.top().first < d) {
    pair<int,int> p = degrees.top(); degrees.pop();
    int v = p.second;
    if(is_ok[v]) {
      //fprintf(stderr,"Wierzcholek nr %2d ma stopien %d < %d - wywalamy!\n", v, p.first, d);
      is_ok[v] = false;
      for(set<int>::iterator it = graph[v].begin(); it != graph[v].end(); ++it) {
        int u = *it;
        //fprintf(stderr,"  Likwidujemy droge do miasta %d\n", u);
        graph[u].erase(v);
        //fprintf(stderr,"    Wierzcholek %d ma teraz stopien %d\n", u, graph[u].size());
        degrees.push(make_pair(graph[u].size(), u));
      }
      graph[v].clear();  
    }
  }

  /*/////////////////////////////////////////////////////////////////////////////
  for(int i=1; i<=n; ++i) {
    fprintf(stderr,"Wierzcholek nr %2d ma stopien %d. Ok? - %s\n", i, graph[i].size(), (is_ok[i] ? "true" : "false"));
  }
  /*/////////////////////////////////////////////////////////////////////////////

  vector<vector<int> > components;
  vector<bool> visited(n+1, false);
  for(int i=1; i<=n; ++i) {
    if(!visited[i] && is_ok[i]) {
      //fprintf(stderr,"Miasto %d jest ok i jeszcze nie odwiedzone!\n", i);
      //fprintf(stderr,".\n.\n.\n. . . . . . . . . NOWA SKLADOWA:\n");
      vector<int> new_component;
      visit(i, graph, visited, new_component);
      //fprintf(stderr,". . . . . . . . . KONIEC SKLADOWEJ\n.\n.\n.\n");
      components.push_back(new_component);
    }
  }

  //fprintf(stderr,"Liczba skladowych: %d\n", components.size());
  if(components.size() == 0) {
    printf("NIE\n");
  } else {
    int max_component_index = 0;
    for(int i=1; i<components.size(); ++i) {
      if(components[i].size() > components[max_component_index].size()) {
        //fprintf(stderr,"Skladowa nr %d jest wieksza niz %d\n", i, max_component_index);
        max_component_index = i;
      }
    }

    vector<int>& max_component = components[max_component_index];
    sort(max_component.begin(), max_component.end());
    printf("%d\n", max_component.size());
    for(int i=0; i<max_component.size(); ++i) {
      printf("%d ", max_component[i]);
    }
    printf("\n");
  }

  return 0;
}