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
#include <cstdio>
#include <algorithm>
#include <stack>
using namespace std;


int N, M, D;

struct Edge {
    int v;
    int next;
};

Edge E[400000];
int V[200000];
int S[200000];
int P[200000];
int bestp, K;


void load() {
    scanf("%d%d%d", &N, &M, &D);
    fill(S, S+N, 0);
    fill(V, V+N, -1);
    for (int i=0; i<M; i++) {
        int a, b; scanf("%d%d", &a, &b); a--, b--;
        E[2*i].v = b;
        E[2*i].next = V[a];
        V[a] = 2*i;
        E[2*i+1].v = a;
        E[2*i+1].next = V[b];
        V[b] = 2*i+1;
        S[a]++, S[b]++;
    }
}


void remove_bad() {
    stack<int> bads;
    for (int i=0; i<N; i++)
        if (S[i] < D)
            bads.push(i);
    
    while (!bads.empty()) {
        int v = bads.top(); bads.pop();
        for (int e = V[v]; e != -1; e = E[e].next) {
            int u = E[e].v;
            S[u]--;
            if (S[u] == D-1)
                bads.push(u);
        }
    }
}


int divide() {
    bestp = -1;
    K = 0;

    fill(P, P+N, -1);
    for (int v=0; v<N; v++) {
        if (P[v] != -1 || S[v] < D)
            continue;
        
        int size = 0;
        stack<int> part;
        part.push(v);
        P[v] = v;
        while (!part.empty()) {
            int u = part.top(); part.pop();
            size++;
            if (size > K)
                bestp = v, K = size;
            
            for (int e = V[u]; e != -1; e = E[e].next) {
                int w = E[e].v;
                if (P[w] != -1 || S[w] < D)
                    continue;
                part.push(w);
                P[w] = v;
            }
        }
    }
}


void save() {
    if (K == 0) {
        printf("NIE\n");
        return;
    }
    
    printf("%d\n", K);
    for (int i=0; i<N; i++)
        if (P[i] == bestp)
            printf("%d ", i+1);
    printf("\n");
}


int main() {
    load();
    
    remove_bad();
    
    divide();
    
    save();
    
    return 0;
}