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

void dfs(unsigned v, std::vector<std::vector<unsigned>> const& G, std::vector<bool> & del, std::vector<unsigned> & res) {
    if(del[v]) return;

    res.push_back(v);
    del[v] = true;

    for(auto w : G[v]) dfs(w, G, del, res);
}

int main() {
    std::ios_base::sync_with_stdio(false);

    unsigned n, m, d;
    std::cin >> n >> m >> d;
    n += 1;

    std::vector<std::vector<unsigned>> G(n);

    for(unsigned i = 1; i <= m; i++) {
        unsigned a, b;
        std::cin >> a >> b;

        G[a].push_back(b);
        G[b].push_back(a);
    }

    std::vector<bool> del(n, false);
    std::vector<unsigned> deg(n);
    std::queue<unsigned> to_del;

    for(unsigned i = 0; i < n; i++) {
        deg[i] = G[i].size();
        if(deg[i] < d) to_del.push(i);
    }

    while(!to_del.empty()) {
        unsigned v = to_del.front();
        to_del.pop();
        del[v] = true;

        for(auto w : G[v]) {
            deg[w] --;
            if(deg[w] + 1 == d) to_del.push(w);
        }
    }

    std::vector<unsigned> best;
    std::vector<unsigned> tmp_best;

    for(unsigned i = 1; i < n; i++) {
        tmp_best.clear();

        dfs(i, G, del, tmp_best);

        if(tmp_best.size() > best.size()) std::swap(tmp_best, best);
    }

    if(best.size() == 0) {
        std::cout << "NIE" << std::endl;
    } else {
        std::cout << best.size() << std::endl;
        std::sort(std::begin(best), std::end(best));
        for(unsigned v : best) {
            std::cout << v << " ";
        }
        std::cout << std::endl;
    }
}