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
140
141
142
143
#ifdef _MSC_VER
  #ifndef __GNUC__
    #pragma warning(disable: 4996)
  #endif
  #define main main0
#endif
#include <iomanip>
#include <iostream>
using namespace std;

struct Road;

struct City {
  long roads;               // liczba drog
  Road* target;             // droga do miasta
  long number_set;          // numer zbioru miast
};

struct Road {
  City* target;
  Road* next;
};

static const long Max = 200001;
City cities[Max];           // miasta
Road roads[Max*2];          // drogi
City* list_cities[Max];     // miasta o zbyt malej ilosci drog
long size_of_set[Max];      // liczebnosc zbioru miast

void ReadRoads(long m) {
  Road* last_road = roads;

  for(long i = 0; i < m; ++i) {           // wczytywanie drog
    long a, b;
    cin >> a >> b;
    ++cities[a].roads;
    last_road->target = cities + b;
    last_road->next = cities[a].target;
    cities[a].target = last_road++;
    ++cities[b].roads;
    last_road->target = cities + a;
    last_road->next = cities[b].target;
    cities[b].target = last_road++;
  }
}

void PrintCities(long n) {
  cout << "nr  roads num_set target\n";
  for(long i = 1; i <= n; ++i) {
    cout << setw(2) << i << setw(4) << cities[i].roads << setw(6) << cities[i].number_set << "    ";
    for(Road* road = cities[i].target; road != 0; road = road->next)
      cout << setw(3) << road->target - cities;
    cout << '\n';
  }
  cout << '\n';
}

void FindCityTooFewRoads(long n, long d) {
  City** last_bad_city = list_cities;
  fill(list_cities, list_cities + n, static_cast<City*>(0));

  for(City* citi = cities + 1; citi <= cities + n; ++citi)  // miasta ze zbyt mala liczba drog
    if(citi->number_set == 0 && citi->roads < d) {
      citi->number_set = - 1;
      *last_bad_city = citi;
      ++last_bad_city;
    }

  for(City** city = list_cities; *city != 0 ; ++city) {  // usuwanie drog od zlych miast, usuwanie nowych zlych miast
    for(Road* road = (*city)->target; road != 0; road = road->next) {
      if(road->target->number_set == 0 && --road->target->roads < d) {
        road->target->number_set = - 1;
        *last_bad_city = road->target;
        ++last_bad_city;
      }
    }
  }
}

void SetCollectionsCities(long n) {
  long number_of_sets = 0;
  City** city = list_cities;
  fill(list_cities, list_cities + n, static_cast<City*>(0));

  for(long i = 1; i <= n; ++i) {          // BFS - przeszukiwanie wszerz
    if(cities[i].number_set == 0) {
      cities[i].number_set = ++number_of_sets;
      ++size_of_set[number_of_sets];
      *city++ = cities + i;
      while(city != list_cities) {
        City* current = *--city;
        for(Road* road = current->target; road != 0; road = road->next) {
          if(road->target->number_set == 0) {
            *city++ = road->target;
            road->target->number_set = number_of_sets;
            ++size_of_set[number_of_sets];
          }
        }
      }
    }
  }
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);

  long m, n, d;

  cin >> n >> m >> d;
#ifdef _MSC_VER
  fill(cities + 1, cities + n + 1, City());
  fill(size_of_set, size_of_set + n, 0);
#endif
  ReadRoads(m);                           // wczytywanie drog
  //PrintCities(n);

  FindCityTooFewRoads(n, d);
  //PrintCities(n);

  SetCollectionsCities(n);
  //PrintCities(n);

  long number_max_collections = 0;
  for(long i = 1, j = 0; size_of_set[i] > 0; ++i) {
    if(j < size_of_set[i]) {
      j = size_of_set[i];
      number_max_collections = i;
    }
  }

  if(size_of_set[number_max_collections] == 0)
    cout << "NIE" << endl;
  else {
    cout << size_of_set[number_max_collections] << '\n';
    for(long i = 1; i <= n; ++i)
      if(cities[i].number_set == number_max_collections)
        cout << i << ' ';
    cout << endl;
  }

  return 0;
}