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
#include <stdio.h>
typedef struct SEdge SEdge;

struct SEdge{
    int v;
    SEdge *next;
};

SEdge *node[200004], data[400008];
int deg[200004], heap[200004], pos[200004];
int visi[200004], T[200004];

void merge(int *t, int p, int q, int v){
    int i = p, j = q + 1;
    while (!(i > v)){ T[i] = t[i]; i++; } i = p;
    while ( !(p > q) && !(j > v) ){
        if(deg[T[p]] < deg[T[j]]){
            pos[T[p]] = i;
            t[i++] = T[p++];
        }
        else{
            pos[T[j]] = i;
            t[i++] = T[j++];
        }
    }
    while ( !(p > q) ){
        pos[T[p]] = i;
        t[i++] = T[p++];
    }
}

void mergeSort(int *t, int p, int v){
    if (p < v){
        int q = (p + v)>>1;
        mergeSort(t, p, q);
        mergeSort(t, q+1, v);
        merge(t, p, q, v);
    }
}

int DFS(int v, int l){
    SEdge *tmp;
    int n = 0, L = 0;
    heap[L++] = v;
    while(L){
        v = heap[--L];
        if(!visi[v]){
            visi[v] = l;
            n++;
            tmp = node[v];
            while(tmp){
                if(pos[tmp->v] && !visi[tmp->v]) heap[L++] = tmp->v;
                tmp = tmp->next;
            }
        }
    }
    return n;
}

int main()
{
    SEdge *tmp;
    int n, m, d, a, b, t = 0, i, j, k;

    scanf("%d%d%d",&n,&m,&d);

    for(i = 1; i <= n; i++)
        pos[i] = heap[i] = i;

    while(m--){
        scanf("%d%d",&a,&b);
        data[t].v = b;
        data[t].next = node[a];
        node[a] = &data[t++];
        data[t].v = a;
        data[t].next = node[b];
        node[b] = &data[t++];
        deg[a]++;
        deg[b]++;
    }

    m = n;
    mergeSort(heap, 1, m);

    while(m > 0 && deg[heap[1]] < d){
        i = heap[1];
        j = 2, k = heap[m--];
        while(j <= m){
            if(j^m && deg[heap[j+1]] < deg[heap[j]]) j++;
            if(deg[k] <= deg[heap[j]]) break;
            heap[j>>1] = heap[j];
            pos[heap[j]] = j>>1;
            j <<= 1;
        }
        heap[j>>1] = k;
        pos[k] = j>>1;
        pos[i] = 0;
        tmp = node[i];
        while(tmp){
            if( pos[tmp->v] ){
                deg[tmp->v]--;
                j = pos[tmp->v], k = heap[j];
                while(j > 1 && deg[heap[j>>1]] > deg[k]){
                    heap[j] = heap[j>>1];
                    pos[heap[j]] = j;
                    j >>= 1;
                }
                heap[j] = k;
                pos[k] = j;
            }
            tmp=tmp->next;
        }
    }

    t = b = m = 0;
    for(i = 1; i <= n; i++){
        if(pos[i] && !visi[i]){
            j = DFS(i,++t);
            if(j > m){
                b = t;
                m = j;
            }
        }
    }

    if(t > 0){
        printf("%d\n",m);
        for(i = 1; i <= n; i++){
            if(visi[i] == b) printf("%d ",i);
        }
    }
    else printf("NIE\n");



    return 0;
}