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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

const int maxN = 500000;

vector <int> G[maxN + 1], res_vertices;
bool vis[maxN + 1], banned[maxN + 1];
int limit, current_component_size, state[maxN + 1];
queue <int> Q;

void kinda_top_sort()
{
    while (!Q.empty())
    {
        int v = Q.front();
        Q.pop();

        for (int i=0; i<G[v].size(); i++)
        {
            int u = G[v][i];

            if (banned[u])
                continue;

            state[u]--;

            if (state[u] >= limit)
                continue;

            banned[u] = 1;
            Q.push(u);
        }
    }
}

void dfs(int v, bool flag)
{
    if (flag)
        res_vertices.push_back(v);

    else
        current_component_size++ ;

    vis[v] = 1;

    for (int i=0; i<G[v].size(); i++)
    {
        int u = G[v][i];

        if (banned[u] or vis[u])
            continue;

        dfs(u, flag);
    }
}

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

    while (m--)
    {
        int a, b;
        scanf ("%d%d", &a, &b);

        G[a].push_back(b);
        G[b].push_back(a);
    }

    for (int i=1; i<=n; i++)
    {
        state[i] = G[i].size();

        if (state[i] >= limit)
            continue;

        banned[i] = 1;
        Q.push(i);
    }

    kinda_top_sort();

    int res_component_size = 0, res_main_vertex = 0;

    for (int i=1; i<=n; i++)
    {
        if (banned[i] or vis[i])
            continue;

        dfs(i, 0);

        if (res_component_size < current_component_size)
        {
            res_component_size = current_component_size;
            res_main_vertex = i;
        }

        current_component_size = 0;
    }

    if (res_component_size == 0)
    {
        printf("NIE\n");
        return 0;
    }

    fill (vis + 1, vis + 1 + n, 0);

    dfs(res_main_vertex, 1);

    sort(res_vertices.begin(), res_vertices.end());

    printf("%d\n", res_component_size);

    for (int i=0; i<res_component_size; i++)
        printf("%d ", res_vertices[i]);

    return 0;
}