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 <cstdio>
#include <vector>
#include <set>

int n, m, d, a, b, size[200001], r, p, id[200001];
bool inside[200001], visited[200001];
std::vector<int> G[200001];

struct cmp {
    bool operator() (int a, int b) {
        if (size[a] < size[b])
            return true;

        if (size[b] < size[a])
            return false;

        return a < b;
    }
};
std::set<int, cmp> S;

int dfs_size(int v, int p, int _id) {
    if (visited[v])
        return 0;

    visited[v] = true;
    id[v] = _id;

    int r = 0;

    for (int i = 0; i < G[v].size(); i ++) {
        if (G[v][i] == p || !inside[G[v][i]])
            continue;
        r += dfs_size(G[v][i], v, _id);
    }
    return r+1;
}

int main () {
    scanf("%d %d %d", &n, &m, &d);
    while (m--) {
        scanf("%d %d", &a, &b);
        G[a].push_back(b);
        G[b].push_back(a);
    }

    for (int i = 1; i <= n; i ++) {
        size[i] = G[i].size();
        S.insert(i);
        inside[i] = true;
    }

    while(S.size() > 0 && size[*S.begin()] < d) {
        int cur = *S.begin();

        for (int i = 0; i < G[cur].size(); i ++) {
            if (!inside[G[cur][i]])
                continue;

            S.erase(G[cur][i]);
            size[G[cur][i]] --;
            S.insert(G[cur][i]);
        }

        S.erase(cur);
        inside[cur] = false;
    }

    if (S.size() == 0) {
        printf("NIE\n");
        return 0;
    }

    for (int i = 1; i <= n; i ++) {
        if (!visited[i] && inside[i]) {
            int tmp = dfs_size(i, -1, i);
            if (r < tmp) {
                r = tmp;
                p = i;
            }
        }
    }

    printf("%d\n", r);
    for (int i = 1; i <= n; i ++)
        if (id[i] == p)
            printf("%d ", i);
    printf("\n");
    return 0;
}