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
#include<bits/stdc++.h>
#define ALL(X)        X.begin(),X.end()
#define FOR(I,A,B)    for(int (I) = (A); (I) <= (B); (I)++)
#define FORW(I,A,B)   for(int (I) = (A); (I) < (B);  (I)++)
#define FORD(I,A,B)   for(int (I) = (A); (I) >= (B); (I)--)
#define FOREACH(I,A)  for(__typeof(A.begin()) I = A.begin(); I != A.end(); ++I)
#define CLEAR(X)      memset(X,0,sizeof(X))
#define SIZE(X)       int(X.size())
#define CONTAIN(A,X)  (A.find(X) != A.end())
#define PB            push_back
#define MP            make_pair
#define X             first
#define Y             second
#define LBOUND(P,R,Q) ({__typeof(P) X=P,RR=(R), PP = P; while(PP<RR) {X = (PP+(RR-PP)/2); if(Q) RR = X; else PP = X+1;} PP;})
using namespace std;
typedef signed long long slong;
typedef long double ldouble;
const slong Infinity = 1000000100;
const ldouble Epsilon = 1e-9;
template<typename T, typename U> ostream& operator << (ostream& os, const pair<T,U>&p) { return os << "(" << p.X << "," << p.Y << ")"; }
template<typename T> ostream& operator << (ostream &os, const vector<T>& V) { os << "["; FORW(i,0,SIZE(V)) os << V[i] << ((i==SIZE(V)-1) ? "" : ","); return os << "]"; }
template<typename T> ostream& operator << (ostream &os, const set<T>& S) {os << "("; FOREACH(i,S) os << *i << (*i==*S.rbegin()?"":","); return os << ")"; }
template<typename T, typename U> ostream& operator << (ostream &os, const map<T, U>& M){os << "{"; FOREACH(i,M) os << *i << (*i.X==M.rbegin()->X?"":","); return os << "}"; }

const int MAXN = 1000100;
int N, M, K;
vector<int> G[MAXN];

void read_data() {
    scanf("%d %d %d", &N, &M, &K);
    FOR(i,1,M) {
        int a, b;
        scanf("%d %d", &a, &b);
        G[a].PB(b);
        G[b].PB(a);
    }
}

int D[MAXN];
bool O[MAXN];

bool V[MAXN];
vector<int> S;
void dfs(int v) {
    V[v] = true;
    S.PB(v);
    for(int u: G[v]) if(!V[u] and !O[u]) dfs(u);
}

void solve() {
    FOR(i,1,N) D[i] = SIZE(G[i]);
    queue<int> Q;
    FOR(i,1,N) if(D[i] < K) {
        O[i] = true;
        Q.push(i);
    }
    while(!Q.empty()) {
        int v = Q.front();
        Q.pop();
        for(int u: G[v]) if(!O[u]) {
            --D[u];
            if(D[u] < K) {
                O[u] = true;
                Q.push(u);
            }
        }
    }
    vector<int> R;
    FOR(i,1,N) {
        if(!O[i] and !V[i]) {
            S.clear();
            dfs(i);
            if(SIZE(S) > SIZE(R)) R = S;
        }
    }

    if(R.empty()) {
       printf("NIE\n"); 
    } else {
        printf("%d\n", SIZE(R));
        for(int r: R) printf("%d ", r);
        printf("\n");
    }
}

int main() {
    read_data();
    solve();
    return 0;
}