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

struct node_t
{
        int idx;
        int count;
        int value;
};

void set_val(std::vector<node_t>& gg, std::vector<std::vector<int>>& g, std::vector<std::vector<int>>& ret, int n, int val) {
        if (gg[n].value != 0)
                return;
        ret.back().push_back(n);
        gg[n].value = val;
        for (auto s: g[n]) {
                set_val(gg, g, ret, s, val);
        }
}

void remove_below_d(std::vector<node_t>& gg, std::vector<std::vector<int>>& g, int n, int d) {
        if (gg[n].value != 0 || gg[n].count >= d)
                return;

        gg[n].value = -1;

        for (auto s: g[n]) {
                --gg[s].count;
                remove_below_d(gg, g, s, d);
        }
}


int main() {
        int n, m, d;
        scanf("%d%d%d", &n, &m, &d);
        ++n;

        std::vector<std::vector<int>> g(n);
        std::vector<node_t> gg(n);
        for (int i = 1; i < n; ++i) {
                gg[i] = {i, 0, 0};
        }

        for (int i = 0; i < m; ++i) {
                int v1, v2;
                scanf("%d%d", &v1, &v2);
                g[v1].push_back(v2);
                ++gg[v1].count;
                g[v2].push_back(v1);
                ++gg[v2].count;
        }

        for (int i = 1; i < n; ++i) {
                remove_below_d(gg, g, i, d);
        }

        std::vector<std::vector<int>> ret;
        for (int i = 1; i < n; ++i) {
                if (gg[i].value == 0) {
                        ret.push_back({});
                        set_val(gg, g, ret, i, i);
                }
        }
        size_t best = 0;
        size_t idx = 0;
        for (size_t i = 0; i < ret.size(); ++i) {
                if (ret[i].size() > best) {
                        best = ret[i].size();
                        idx = i;
                }
        }
        if (best == 0) {
                printf("NIE\n");
        }
        else {
                printf("%zu\n", ret[idx].size());
                std::sort(ret[idx].begin(), ret[idx].end());
                for (auto r: ret[idx])
                        printf("%d ", r);
                printf("\n");
        }
}