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
#include <stdio.h>

struct {
    int edges, *list, mark;
} nodes[200000];

struct {
    int a, b;
} edges[200000];

int mem[200000], stack[200000], sp=0;

int n, m, d;

int find(int mark) {
    int i, a, b, num=0;
    for(i=0; i<n; ++i)
        if(nodes[i].mark==0)
            break;
    if(i==n)
        return 0;
    stack[0]=i;
    sp=1;
    nodes[i].mark=mark;
    while(sp) {
        a=stack[--sp];
        for(i=0; i<nodes[a].edges; ++i) {
            b=nodes[a].list[i];
            if(nodes[b].mark!=0)
                continue;
            nodes[b].mark=mark;
            stack[sp++]=b;
        }
        ++num;
    }
    return num;
}

int main() {
    int i, j, a, b;
    int cur_size, max_size=0, max_mark=-1;
    scanf("%d %d %d", &n, &m, &d);
    for(i=0; i<n; ++i) {
        nodes[i].edges=0;
        nodes[i].mark=0;
    }
    for(i=0; i<m; ++i) {
        scanf("%d %d", &edges[i].a, &edges[i].b);
        ++nodes[--edges[i].a].edges;
        ++nodes[--edges[i].b].edges;
    }
    for(i=0, j=0; i<n; ++i) {
        nodes[i].list=mem+j;
        j+=nodes[i].edges;
    }
    for(i=0; i<n; ++i)
        nodes[i].edges=0;
    for(i=0; i<m; ++i) {
        a=edges[i].a;
        b=edges[i].b;
        nodes[a].list[nodes[a].edges++]=b;
        nodes[b].list[nodes[b].edges++]=a;
    }
    for(i=0; i<n; ++i) {
        if(nodes[i].edges<d) {
            stack[sp++]=i;
            nodes[i].mark=-1;
        }
    }
    while(sp) {
        a=stack[--sp];
        for(i=0; i<nodes[a].edges; ++i) {
            b=nodes[a].list[i];
            if(nodes[b].mark!=0)
                continue;
            for(j=0; nodes[b].list[j]!=a; ++j)
                ;
            for(++j; j<nodes[b].edges; ++j)
                nodes[b].list[j-1]=nodes[b].list[j];
            if(--nodes[b].edges<d) {
                nodes[b].mark=-1;
                stack[sp++]=b;
            }
        }
    }
    for(i=1; (cur_size=find(i))>0; ++i) {
        if(cur_size>max_size) {
            max_size=cur_size;
            max_mark=i;
        }
    }
    if(max_size<d) {
        printf("NIE\n");
    } else {
        printf("%d\n", max_size);
        for(i=0; i<n; ++i)
            if(nodes[i].mark==max_mark)
                printf("%d ", i+1);
        printf("\n");
    }
    return 0;
}