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
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 200000 + 5;

int ile_kr[MAXN];
int usuniete[MAXN];

struct Kr{
       int x;
       int y;    
};

class compare {
      public: 
               bool operator() (const Kr a, const Kr b) 
               {
                    if (a.x == b.x) return a.y < b.y;   
                    return a.x < b.x;
               }
};

vector<Kr> v;
int pocz[MAXN];

vector<int> za_malo_stos; 
int za_malo_tab[MAXN];

int n,m,d; 

vector<int> akt_v;
vector<int> max_v;
  
vector<int> stos;
int odw[MAXN];


int main(int argc, char *argv[]) {        
    scanf("%d %d %d", &n, &m, &d);

    for (int i = 0; i < m ; i++) {
          Kr kr;
          int a, b;
          scanf("%d %d", &a, &b);
          
          ile_kr[a]++;
          ile_kr[b]++;
    
          kr.x = a;
          kr.y = b;
          
          v.push_back(kr);
          
          kr.x = b;
          kr.y = a;
          
          v.push_back(kr);
    }
    
    Kr kr;	
    
    sort(v.begin(), v.end(), compare());
    
    for (int i = 1 ; i <= n ; i++){
          pocz[i] = -1;
    }
    
    for (int i = v.size() - 1; i >= 0 ; i--) {
        kr = v[i];
        pocz[kr.x] = i;  
    }
       
    for (int i = 1;  i <= n ; i++) {
        if (ile_kr[i] < d)  {
           za_malo_stos.push_back(i);
           za_malo_tab[i] = 1;   
        }
    }
   
    while (!za_malo_stos.empty()) {
          int w = za_malo_stos.back();
          za_malo_stos.pop_back();   
          
          if (pocz[w] == -1)  continue;
          
          for (int i = pocz[w]; w == v[i].x ;i++) {
               int y = v[i].y;
               ile_kr[y]--;
               
               if (ile_kr[y] < d && za_malo_tab[y]==0) {
                     za_malo_stos.push_back(y);
                     za_malo_tab[y] = 1;           
               }
          }
    }
        
    for (int i = 1; i <= n; i++) {
        
        if (odw[i]==0 && za_malo_tab[i] == 0) {
            akt_v.clear();
            
            stos.clear();
            stos.push_back(i);
            odw[i] = 1;
            
            while (!stos.empty()) {
                 int x = stos.back();
                 stos.pop_back();  
                 
                 akt_v.push_back(x);
                              
                 for (int i = pocz[x]; x == v[i].x ;i++) {
                     int y = v[i].y;
               
                     if (za_malo_tab[y]==0 && odw[y]==0) {
                          stos.push_back(y);
                          odw[y] = 1;           
                     } 
                 }
            }      
            
            if (akt_v.size() > max_v.size()) max_v = akt_v;
        } 
    }
    
    if (max_v.size()==0) {
        cout << "NIE"<< endl;                
    }  else {
       printf("%d\n", max_v.size());  
       
       sort(max_v.begin(), max_v.end()); 
       
       for (int i = 0; i < max_v.size() ; i++) {
           printf("%d ", max_v[i]);
       }
    }
    
    return 0;
}