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
/* Marcin 'Gregor' Gregorczyk
 * PA 2015, runda 2, zadanie Mistrzostwa */

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

#define rank RANK

const int MAXN = 200009;

int n, m, d;
int rank[MAXN];
bool visit[MAXN];
vector<int> graph[MAXN];
vector<int> finalGraph[MAXN];

int bfs(int start, bool save, vector<int>& result);
void read_graph();
void transform_graph();
void solve();

int main() {
  read_graph();
  transform_graph();
  solve();
  return 0;
}

int bfs(int start, bool save, vector<int>& result) {
  int size = 1;
  queue<int> q;
  visit[start] = true;
  q.push(start);
  if(save) result.push_back(start);
  while(!q.empty()) {
    int w = q.front();
    for(int i = 0; i < finalGraph[w].size(); i++) {
      if(!visit[finalGraph[w][i]]) {
        visit[finalGraph[w][i]] = true;
        q.push(finalGraph[w][i]);
        size++;
        if(save) result.push_back(finalGraph[w][i]);
      }
    }
    q.pop();
  }
  return size;
}

void read_graph() {
  int edgeA, edgeB;
  scanf("%d%d%d", &n, &m, &d);
  for(int i = 0; i < m; i++) {
    scanf("%d%d", &edgeA, &edgeB);
    rank[edgeA]++;
    rank[edgeB]++;
    graph[edgeA].push_back(edgeB);
    graph[edgeB].push_back(edgeA);
  }
}

void transform_graph() {
  queue<int> q;
  for(int i = 1; i <= n; i++)
    if(rank[i] < d)
      q.push(i);
  
  while(!q.empty()) {
    int w = q.front();
    rank[w] = -1;
    for(int i = 0; i < graph[w].size(); i++) {
      rank[graph[w][i]]--;
      if(rank[graph[w][i]] == d-1) {
        q.push(graph[w][i]);
        rank[graph[w][i]] = -1;
      }
    }
    q.pop();
  }

  for(int i = 1; i <= n; i++)
    if(rank[i] > 0)
      for(int j = 0; j < graph[i].size(); j++)
        if(rank[graph[i][j]] > 0)
          finalGraph[i].push_back(graph[i][j]);
  
}

void solve() {
  int result = 0, resultVertex = 0;
  vector<int> rList;
  for(int i = 1; i <= n; i++) {
    if(rank[i] > 0 && !visit[i]) {
      int size = bfs(i, false, rList);
      if(size > result) {
        result = size;
        resultVertex = i;
      }
    }
  }
  if(result < 2)
    printf("NIE\n");
  else {
    for(int i = 1; i <= n; i++)
      visit[i] = false;
    bfs(resultVertex, true, rList);
    sort(rList.begin(), rList.end());
    printf("%d\n", result);
    for(int i = 0; i < rList.size(); i++)
      printf("%d ", rList[i]);
  }
}