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 <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
#include <cassert>
using namespace std;

constexpr int MAXN = 200010;

int N, D;
bool removed[MAXN];
vector<int> neighbours[MAXN];
int deg[MAXN];
queue<int> throwem_out;
vector<int> result;
bool visited[MAXN]; // could also use removed instead


void read_data() {
    int m;
    scanf("%d%d%d", &N, &m, &D);
    for (int i = 0; i < m; ++i) {
        int a, b;
        scanf("%d%d", &a, &b);
        --a; --b;
        neighbours[a].push_back(b);
        neighbours[b].push_back(a);
        ++deg[a];
        ++deg[b];
    }
}

void remove_infidels() {
    for (int i = 0; i < N; ++i) {
        if (deg[i] < D) {
            throwem_out.push(i);
//             printf("pushed %d\n", i);
        }
    }

    while (!throwem_out.empty()) {
        int curr = throwem_out.front();
        throwem_out.pop();
        if (removed[curr]) {
            continue;
        }
        removed[curr] = true;
        for (auto nei : neighbours[curr]) {
//             printf("%d -> %d (%d)\n", curr, nei, removed[nei]);
            if (removed[nei]) {
                continue;
            }
            --deg[nei];
            if (deg[nei] < D) {
                throwem_out.push(nei);
//                 printf("pushed %d\n", nei);
            }
        }
    }
}

void find_component_rec(int node) {
    if (visited[node]) {
        return;
    }
    visited[node] = true;
    result.push_back(node);
    for (int nei : neighbours[node]) {
        if (!removed[nei] && !visited[nei]) {
            find_component_rec(nei);
        }
    }
}

void find_component() {
    vector<int> best;
    for (int i = 0; i < N; ++i) {
        if (!removed[i] && !visited[i]) {
            find_component_rec(i);
            if (result.size() > best.size()) {
                best = std::move(result);
                assert(result.empty());
            }
            result.clear();
        }
    }
    if (best.empty()) {
        printf("NIE\n");
        return;
    }
    sort(best.begin(), best.end());
    printf("%d\n", best.size());
    for (int node : best) {
        printf("%d ", node + 1);
    }
    printf("\n");
}


int main() {
    read_data();
    remove_infidels();
    find_component();
}