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
#include <iomanip>
#include <iostream>
#include <utility>
#include <algorithm>
#include <queue>
#include <cassert>
#include <string>
#include <vector>
#include <set>
#include <map>

using namespace std;

#define ALL(x) x.begin(), x.end()
#define VAR(a,b) __typeof (b) a = b
#define IN(a) int a; cin >> a
#define IN2(a,b) int a, b; cin >> a >> b
#define REP(i,n) for (int _n=(n), i=0; i<_n; ++i)
#define FOR(i,a,b) for (int _b=(b), i=(a); i<=_b; ++i)
#define FORD(i,a,b) for (int _b=(b), i=(a); i>=_b; --i)
#define FORE(i,a) for (VAR(i,a.begin ()); i!=a.end (); ++i) 
#define PB push_back
#define MP make_pair
#define ST first
#define ND second

typedef vector<int> VI;
typedef long long LL;
typedef pair<int,int> PII;
typedef double LD;

const int DBG = 0, INF = int(1e9);

int main() {
   ios_base::sync_with_stdio(0);
   cout.setf(ios::fixed);
   int n, m, d; cin >> n >> m >> d;
   vector<VI> v(n);
   VI deg(n, 0);
   REP(q,m) {
     IN2(a,b);
     --a; --b;
     v[a].PB(b);
     v[b].PB(a);
     ++deg[a];
     ++deg[b];
   }
   queue<int> rem;
   vector<bool> is_removed(n, false);
   REP(i,n)
     if (deg[i] < d) {
       rem.push(i);
       is_removed[i] = true;
     }

   while (!rem.empty()) {
     int nxt = rem.front();
     rem.pop();
     FORE(it, v[nxt]) {
       if (--deg[*it] < d && !is_removed[*it]) {
         rem.push(*it);
         is_removed[*it] = true;
       }
     }
   }

   set<int> best;
   vector<int> st;
   REP(i,n)
     if (!is_removed[i]) {
       set<int> cur;
       cur.insert(i);
       is_removed[i] = true;
       st.PB(i);
       while (!st.empty()) {
         int nxt = st.back();
         st.pop_back();
         FORE(it, v[nxt])
           if (!is_removed[*it]) {
             cur.insert(*it);
             is_removed[*it] = true;
             st.PB(*it);
           }
       }
       if (cur.size() > best.size())
         swap(cur, best);
     }

   if (best.empty())
     cout << "NIE\n";
   else {
     cout << best.size() << endl;
     FORE(it, best)
       cout << *it + 1 << " ";
     cout << endl;
   }

   return 0;
}