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
#include <cstdio>
#include <map>
#include <set>
#include <vector>

typedef std::set<int> MSet;
typedef std::vector<MSet> VMap;

void make(int i, MSet &out, VMap &vmap)
{
    if(vmap[i].size() == 0)
        return;
    MSet local = vmap[i];
    vmap[i].clear();
    out.insert(local.begin(), local.end());


//    for(MSet::iterator it = out.begin(); it != out.end(); it++)
//        printf("%d ", *it);
//    printf("\n");

    for(MSet::iterator it = local.begin(); it != local.end(); it++)
        make(*it, out, vmap);
}

int main(void)
{
    MSet out;
    int max = 0;
    VMap vmap(200000);
    MSet doUsuniecia;
    int n, m, d;
    scanf("%d%d%d", &n, &m, &d);
    int a, b;
    while(m--)
    {
        scanf("%d%d", &a, &b);
        vmap[a].insert(b);
        vmap[b].insert(a);
    }
    for(int i = 1; i <= n; i++)
        if(vmap[i].size() && vmap[i].size() < d)
            doUsuniecia.insert(i);

    while(doUsuniecia.size())
    {
        MSet::iterator it = doUsuniecia.begin();
        MSet set = vmap[*it];
        for(MSet::iterator itt = set.begin(); itt != set.end(); itt++)
        {
            vmap[*itt].erase(*it);
            if(vmap[*itt].size() < d)
                doUsuniecia.insert(*itt);
        }
        vmap[*it].clear();
        doUsuniecia.erase(it);
    }

    for(int i = 1; i <=n; i++)
    {
        if(vmap[i].size() == 0)
            continue;
        MSet local = vmap[i];
        vmap[i].clear();
        MSet localOut;
        localOut.insert(local.begin(), local.end());

//        for(MSet::iterator it = localOut.begin(); it != localOut.end(); it++)
//            printf("%d ", *it);
//        printf("\n");

        for(MSet::iterator it = local.begin(); it != local.end(); it++)
            make(*it, localOut, vmap);

        if(localOut.size() > max)
        {
            max = localOut.size();
            out = localOut;
        }
    }

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

    printf("%d\n", max);
    MSet::iterator it = out.begin();
    printf("%d", *it);
    it++;
    for(; it != out.end(); it++)
        printf(" %d", *it);
    printf("\n");
    return 0;
}