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

using namespace std;

vector<int> G[500001];
int deg[500001];
bool removed[500001];
bool visited[500001];
int counter;
vector<int> wynik;

void dfs(int v, bool print) {
    if(print) wynik.push_back(v);
    visited[v]=true;
    counter++;
    for(int j=0; j<G[v].size(); ++j)
        if(!visited[G[v][j]] && !removed[G[v][j]]) dfs(G[v][j],print);
}

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

    fill(deg,deg+n+1,0);
    fill(removed,removed+n+1,false);
    fill(visited,visited+n+1,false);

    int a, b;
    for(int i=0; i<m; ++i) {
        scanf("%d%d",&a,&b);
        G[a].push_back(b);
        G[b].push_back(a);
        deg[a]++; deg[b]++;
    }

    vector<int> sd;
    for(int i=1; i<=n; ++i)
        if(deg[i]<d) sd.push_back(i);

    while(!sd.empty()) {
       int v=sd.back();
       sd.pop_back();
       removed[v]=true;
       for(int j=0; j<G[v].size(); ++j)
           if(!removed[G[v][j]]) {
              deg[G[v][j]]--;
              if(deg[G[v][j]]==d-1)
                 sd.push_back(G[v][j]);
           }
    }

    int counter_max=0; int v_max=0;
    for(int v=1; v <= n; ++v) {
        counter=0;
        if(!visited[v] && !removed[v]) dfs(v,false);
        if(counter > counter_max) {
            counter_max=counter;
            v_max=v;
        }
    }

    if(counter_max==0) printf("%s\n","NIE");
    else {
        printf("%d\n",counter_max);
        fill(visited,visited+n+1,false);
        dfs(v_max,true);
        sort(wynik.begin(),wynik.end());
        for(int i=0; i<wynik.size(); ++i) printf("%d ", wynik[i]);
        printf("\n");
    }

    return 0;
}