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

using namespace std;


void read_data(int n, int m, vector < set <int> > &V, set < pair < int, int > > &S)
{
    for(int i = 0; i < m; i++)
    {
        int a, b;
        scanf("%d %d", &a, &b);
        a--; b--;

        V[a].insert(b);
        V[b].insert(a);
    }

    for(int i = 0; i < n; i++)
        if(!V[i].empty())
            S.insert(make_pair(V[i].size(), i));
}

void throw_bad(int d, set < pair < int, int > > &S, vector < set < int > > &V)
{
    while(!S.empty())
    {
        auto it = S.begin();
        int size_ = it->first;
        int nr = it->second;

        if(size_ < d)
        {
            for(int neigh : V[nr])
            {
                int neigh_size = V[neigh].size();
                S.erase(make_pair(neigh_size, neigh));
                if(--neigh_size)
                    S.insert(make_pair(neigh_size, neigh));
                V[neigh].erase(nr);
            }
            V[nr].clear();
            S.erase(it);
        }
        else break;
    }
}

void dfs(int v, vector < set < int > > &V, vector < bool > &Vis, vector < int > &Comp)
{
    Vis[v] = 1;

    Comp.push_back(v);

    for(int neigh : V[v])
        if(!Vis[neigh])
            dfs(neigh, V, Vis, Comp);
}

void get_components(set < pair < int, int > > &S, int n, vector < set < int > > &V, vector < vector < int > > &Components)
{
    vector < bool > Vis(n, 1);

    for(pair <int, int> p : S)
        Vis[p.second] = 0;

    for(int i = 0; i < n; i++)
        if(!Vis[i])
        {
            vector < int > Comp;
            dfs(i, V, Vis, Comp);
            Components.push_back(Comp);
        }
}

void choose_best_and_print(vector < vector < int > > &Components)
{
    vector < int > best = Components[0];

    for(vector < int > v : Components)
        if(v.size() > best.size())
            best = v;

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

    printf("%d\n", best.size());

    for(int i = 0; i < best.size(); i++)
        printf("%d ", best[i] + 1);
}


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

    vector < set < int > > V(n);
    set < pair < int, int > > S;

    read_data(n, m, V, S);

    throw_bad(d, S, V);

    if(S.size() == 0)
    {
        printf("NIE\n");
        return 0;
    }

    vector < vector < int > > Components;
    get_components(S, n, V, Components);

    choose_best_and_print(Components);

    return 0;
}