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

using namespace std;

int fin(int a, int T[][2]){
    vector <int>kolej;
    while (T[a][0] != a){
        kolej.push_back(a);
        a = T[a][0];
    }
    for (int i=0; i<kolej.size(); i++){
        T[kolej[i]][0] = a;
    }
    return a;
}

void unio(int a, int b, int T[][2]){
    int pa = fin(a,T);
    int pb = fin(b,T);
    if (pa != pb){
        if (T[pa][1] > T[pb][1]){
            T[pb][0] = pa;
            T[pa][1] += T[pb][1];
        }
        else{
            T[pa][0] = pb;
            T[pb][1] += T[pa][1];
        }
    }
}

int main()
{
    int n,m, d;
    cin >> n >> m >> d;

    vector < vector < int > >sasiedzi(n+1,vector <int>() );
    int stopien[n+1];
    for (int i=0; i<n+1; i++) stopien[i] = 0;

    int a,b;
    for (int i=0; i<m; i++){
        cin >> a >> b;
        sasiedzi[a].push_back(b);
        sasiedzi[b].push_back(a);
        stopien[a]++;
        stopien[b]++;
    }

    queue <int> male;
    for (int i=1; i<n+1; i++){
        if (stopien[i] < d) male.push(i);
    }
    while (!male.empty()){
        int akt = male.front();
        male.pop();
        for (int i=0; i<sasiedzi[akt].size(); i++){
            if (stopien[sasiedzi[akt][i]] == d) male.push(sasiedzi[akt][i]);
            stopien[sasiedzi[akt][i]]--;
        }
    }

    int T[n+1][2];
    for (int i=0; i<n+1; i++){
        T[i][0] = i;
        T[i][1] = 1;
    }

    for (int i=1; i<n+1; i++){
        if (stopien[i] >= d){
            for (int j=0; j<sasiedzi[i].size(); j++){
                if (stopien[sasiedzi[i][j]] >= d){
                    unio(i,sasiedzi[i][j],T);
                }
            }
        }
    }

    int maxi = 0;
    int par = 0;
    for (int i=1; i<n+1; i++){
        if (stopien[i] >= d){
            if (T[i][1] > maxi){
                maxi = T[i][1];
                par = i;
            }
        }
    }
    if (maxi == 0) cout << "NIE";
    else{
        cout << maxi << endl;
        for (int i=1; i<n+1; i++){
            if (fin(i,T) == par) cout << i << " ";
        }
    }

}