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

int n, m, d;
int a, b;
vector<int> v[200000];
int deg[200000];
int t[200000];
int qu[200000];

struct cmp {
    bool operator() (const int &el1, const int &el2) {
        if(deg[el1] < deg[el2]) return true;
        else if(deg[el2] < deg[el1]) return false;
        return el1 < el2;
    }
};

set<int, cmp> skm;

//  ~void wypisz() {
    //  ~printf("SET:: ");
    //  ~for(auto it = skm.begin(); it != skm.end(); ++it) {
        //  ~printf("%d ", *it);
    //  ~}
    //  ~printf("\n");
//  ~}

set<int> bfs(int x) {
    int b, e;
    set<int> res;
    qu[b = e = 0] = x;
    t[x] = 1;
    while(b <= e) {
        x = qu[b++];
        res.insert(x);
        for(int i = 0; i < v[x].size(); ++i) {
            if(t[v[x][i]] == 0 && skm.find(v[x][i]) != skm.end()) {
                t[v[x][i]] = t[x] + 1;
                qu[++e] = v[x][i];
            }
        }
    }
    return res;
}

set<int> rozw() {
    set<int> res, tmp;
    
    for(int i = 0; i < n; ++i) {
        if(t[i] == 0 && skm.find(i) != skm.end()) {
            tmp = bfs(i);
        }
        if(res.size() < tmp.size()) 
            res = tmp;
    }
    return res;
}

bool popraw() { //zwraca true jeżeli nie poprawił
    if(skm.empty() || deg[*(skm.begin())] >= d) return true;
    else {
        int w = *(skm.begin());
        skm.erase(skm.begin());
        for(int i = 0; i < v[w].size(); ++i) {
            int old = skm.size();
            skm.erase(v[w][i]);
            deg[v[w][i]]--;
            if(old != skm.size())
                skm.insert(v[w][i]);
        }
    }
    return false;
}

int main() {
    scanf("%d%d%d",&n, &m, &d);
    for(int i = 0; i < m; ++i) {
        scanf("%d%d", &a, &b);
        v[a-1].push_back(b-1);
        v[b-1].push_back(a-1);
    }
    
    for(int i = 0; i < n; ++i) {
        deg[i] = v[i].size();
    }
    
    for(int i = 0; i < n; ++i) {
        skm.insert(i);
    }

    bool koniec = false;
    while(!koniec) {
        koniec = popraw();
    }
    
    if(!skm.empty()) {
        set<int> res = rozw();
        int size = res.size();
        printf("%d\n", size);
        for(auto it= res.begin(); it != res.end(); ++it) {
            printf("%d ", (*it) + 1);
        }
        printf("\n");
    }
    else {
        printf("NIE\n");
    }   
    
return 0;
}