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
//Grzegorz Krzysiak
#include <iostream>
#include <set>
#include <vector>
#include <utility>

using namespace std;

int n, m, d;

vector< vector<int> > G;
vector<int> color;
vector< set<int> > odp;

void dfs(int v){
    if(color[v] == 0) return;
    color[v] = 0;
    odp.back().insert(v);
    for(unsigned int x = 0; x < G[v].size(); x++){
        dfs(G[v][x]);
    }
}

int main(){
    ios_base::sync_with_stdio(0);

    cin >> n >> m >> d;

    G.resize(n);

    vector<int> l(n, 0);
    set<int> S;
    set<int> do_usuniecia;
    color.resize(n, 0);

    for(int x = 0; x < m; x++){
        int a, b;
        cin >> a >> b;
        a--;
        b--;

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

        l[a]++;
        l[b]++;
    }

    for(int x = 0; x < n; x++){
        if(l[x] < d) do_usuniecia.insert(x);
        else S.insert(x);
    }

    while(do_usuniecia.empty() == false){
        int usuwany = *(do_usuniecia.begin());
        do_usuniecia.erase(do_usuniecia.begin());

        for(unsigned int x = 0; x < G[usuwany].size(); x++){
            int cel = G[usuwany][x];
            if(S.find(cel) == S.end()) continue;
            l[cel]--;
            if(l[cel] < d){
                S.erase(cel);
                do_usuniecia.insert(cel);
            }
        }
    }

    if(S.size() == 0){
        cout << "NIE";
        return 0;
    }

    for(set<int>::iterator it = S.begin(); it != S.end(); it++){
        color[*it] = 1;
    }

    for(int x = 0; x < n; x++){
        odp.push_back(set<int>());
        dfs(x);
    }

    unsigned int odp_max = 0, odp_index;

    for(int x = 0; x < n; x++){
        if(odp_max < odp[x].size()){
            odp_max = odp[x].size();
            odp_index = x;
        }
    }

    cout << odp[odp_index].size() << '\n';
    for(set<int>::iterator it = odp[odp_index].begin(); it != odp[odp_index].end(); it++){
        cout << *it+1 << ' ';
    }

    return 0;
}