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
103
104
#include <vector>
#include <deque>
#include <algorithm>
#include <stdio.h>

using namespace std;

bool removed[200005];
bool visited[200005];
vector<vector<int> > edges;

int n, m, d;

int edges_size(int node) {
    int result = 0;
    for (int i=0; i<edges[node].size(); ++i) {
        if (!removed[edges[node][i]]) {
            result++;
        }
    }
    return result;
}

vector<int> calculate_bfs_size(int node) {
    vector<int> result;
    if (!visited[node]) {
        deque<int> q;
        q.push_back(node);
        while (!q.empty()) {
            int current = q.front();
            q.pop_front();
            for (int i = 0; i < edges[current].size(); ++i) {
                int edge_node = edges[current][i];
                if (!removed[edge_node] && !visited[edge_node]) {
                    q.push_back(edge_node);
                    visited[edge_node] = true;
                    result.push_back(edge_node);

                }
            }

        }
    }
    return result;
}

int main() {
    int ai, bi;

    scanf("%d %d %d", &n, &m, &d);
    edges.resize(n);

    for (int i=0; i<m; ++i) {
        scanf("%d %d", &ai, &bi);
        ai--;
        bi--;
        edges[ai].push_back(bi);
        edges[bi].push_back(ai);
    }

    deque<int> rnodes;
    for (int i=0; i<n; ++i) {
        if (edges_size(i) < d) {
            removed[i] = true;
            rnodes.push_back(i);
        }
    }

    while (!rnodes.empty()) {
        int node = rnodes.front();
        rnodes.pop_front();

        for (int i=0; i<edges[node].size(); ++i) {
            int edge_node = edges[node][i];
            if (!removed[edge_node] && edges_size(edge_node) < d) {
                removed[edge_node] = true;
                rnodes.push_back(edge_node);
            }
        }
    }

    vector<int> best;
    for (int i=0; i<n; ++i) {
        if (!removed[i]) {
            vector<int> current = calculate_bfs_size(i);
            if (current.size() > best.size()) {
                best = current;
            }
        }
    }

    if (!best.empty()) {
        printf("%d\n", best.size());
        sort(best.begin(), best.end());
        for (int i=0; i<best.size(); ++i)
            printf("%d ", best[i]+1);
        printf("\n");
    } else {
        printf("NIE\n");
    }


    return 0;
}