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
124
125
126
127
128
129
#include <bits/stdc++.h>

using namespace std;

#define PB push_back
#define FORE(i, t) for(__typeof(t.begin())i=t.begin();i!=t.end();++i)
#define SZ(x) int((x).size())
#define REP(i, n) for(int i=0,_=(n);i<_;++i)
#define FOR(i, a, b) for(int i=(a),_=(b);i<=_;++i)
#define FORD(i, a, b) for(int i=(a),_=(b);i>=_;--i)

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;

const int INF = 1e9 + 9;
const int MAX_N = 200003;

int n, m, d;
vi adj[MAX_N];
int degree[MAX_N];
bool removed[MAX_N];
int colors[MAX_N];

void add_edge(int a, int b) {
    adj[a].PB(b);
    adj[b].PB(a);
    ++degree[a];
    ++degree[b];
}

void remove_edge(int a, int b) {
    --degree[a];
    --degree[b];
}

void remove_bad_vertices() {
    priority_queue <pii> q;
    FOR(i, 1, n) {
        q.push(pii(-degree[i], i));
    }
    while (!q.empty()) {
        pii top = q.top();
        int v = top.second;
        q.pop();
        if (removed[v] || degree[v] >= d) {
            continue;
        }
        removed[v] = true;
        FORE(ut, adj[v]) {
            int u = *ut;
            if (!removed[u]) {
                remove_edge(v, u);
                q.push(pii(-degree[u], u));
            }
        }
    }
}

pii paint_vertices() {
    int best_color = 0;
    int best_size = 0;
    FOR (i, 1, n) {
        colors[i] = 0;
    }
    FOR (color, 1, n) {
        if (removed[color] || colors[color] != 0) {
            continue;
        }
        int color_size = 0;
        queue<int> q;
        colors[color] = color;
        ++color_size;
        q.push(color);
        while (!q.empty()) {
            int i = q.front();
            q.pop();
            FORE(jt, adj[i]) {
                int j = *jt;
                if (!removed[j] && colors[j] == 0) {
                    q.push(j);
                    colors[j] = color;
                    ++color_size;
                }
            }
        }
        if (color_size > best_size) {
            best_size = color_size;
            best_color = color;
        }
    }
    return pii(best_size, best_color);
}

void inline one() {
    scanf("%d%d%d", &n, &m, &d);
    FOR(i, 1, n) {
        degree[i] = 0;
        removed[i] = false;
    }
    REP(j, m) {
        int a, b;
        scanf("%d%d", &a, &b);
        add_edge(a, b);
    }
    remove_bad_vertices();
//    FOR(i, 1, n) {
//        printf("i=%d szadj=%d removed=%d degree=%d\n", i, SZ(adj[i]), (int) removed[i], degree[i]);
//    }
    pii best_size_and_color = paint_vertices();
    int best_size = best_size_and_color.first;
    int best_color = best_size_and_color.second;
    if (best_size > 0) {
        printf("%d\n", best_size);
        FOR (i, 1, n) {
            if (colors[i] == best_color) {
                printf("%d ", i);
            }
        }
        puts("");
    } else {
        puts("NIE");
    }
}

int main() {
    //int z; scanf("%d", &z); while(z--)
    one();
}