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
100
101
102
// Karol Kosinski
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <functional>
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
//#define DEBUG(x...) printf(x)
#define DEBUG(x...)
using namespace std;
const int NX = 200003;

struct vertex {
        int visited, number, adjlen;
};

bool operator < (const vertex &a, const vertex &b) {
        return a.adjlen - b.adjlen > 0;
}

int n, m, d;
vertex G[NX];
vector<int> Adj[NX], Res;

void read_data() {
        scanf("%d%d%d", &n, &m, &d);
        FOR(i,1,m) {
                int a, b;
                scanf("%d%d", &a, &b);
                Adj[a].push_back(b);
                Adj[b].push_back(a);
        }
        FOR(i,1,n) {
                G[i].visited = 0;
                G[i].number = i;
                G[i].adjlen = Adj[i].size();
        }
}

void mark_low_degree_vertices() {
        priority_queue<vertex> P(G + 1, G + n + 1);
        while( not P.empty() ) {
                vertex &g = G[P.top().number];
                int adj = P.top().adjlen;
                P.pop();
                if( adj == g.adjlen and adj < d ) {
                        for( int i : Adj[g.number] ) {
                                if( G[i].visited == -1 )
                                        continue;
                                --G[i].adjlen;
                                P.push(G[i]);
                        }
                        g.visited = -1;
                        DEBUG("- G[%6d] adj(%6d)\n", g.number, adj);
                }
        }
}

void bfs(int source, int val, int mark, function<void(int)> fun) {
        queue<int> Q;
        Q.push(source);
        while( not Q.empty() ) {
                int v = Q.front();
                if( G[v].visited == val ) {
                        for( int i : Adj[v] )
                                Q.push(i);
                        fun(v);
                        G[v].visited = mark;
                }
                Q.pop();
        }
}

void find_the_biggest_component() {
        int biggest, size = 0, big_size = 0;
        FOR(i,1,n) {
                bfs(i, 0, 1, [&size](int j){ ++size; });
                if(size > big_size) {
                        biggest = i;
                        big_size = size;
                }
                DEBUG("*** G[%6d]: %6d\n", i, size);
                size = 0;
        }
        if( big_size == 0 ) {
                printf("NIE\n");
                return;
        }
        bfs(biggest, 1, 2, [](int j){ Res.push_back(j); });
        sort(Res.begin(), Res.end());
        printf("%d\n", big_size);
        for( int i : Res )
                printf("%d ", i);
        printf("\n");
}

int main() {
        read_data();
        mark_low_degree_vertices();
        find_the_biggest_component();
        return 0;
}