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
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for (int i = (a); i <= (b); ++i)
#define REPD(i,a,b) for (int i = (a); i >= (b); --i)
#define FORI(i,n) REP(i,1,n)
#define FOR(i,n) REP(i,0,int(n)-1)
#define mp make_pair
#define pb push_back
#define sz(x) int((x).size())
#define dbg(v) cerr << #v << " = " << (v) << endl;
#define FOREACH(i,t) for (__typeof(t.begin()) i = t.begin(); i != t.end(); ++i)
#define fi first
#define se second
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef long long ll;

const int MAXN = 200100;
vector<int> g[MAXN];
int degs[MAXN];
int visited[MAXN];
bool good[MAXN];
set<pair<int,int> >::iterator its[MAXN];

set<pair<int,int> > heap;

int main() {
    int n,m,d;
    scanf("%d %d %d", &n, &m, &d);
    FOR(i, m) {
        int a,b;
        scanf("%d %d", &a, &b);
        a--;
        b--;
        g[a].pb(b);
        g[b].pb(a);
    }
    FOR(i,n) {
        degs[i] = g[i].size();
        its[i] = heap.insert(mp(degs[i],i)).first;
    }
    while (!heap.empty() && heap.begin()->first < d) {
        pair<int,int> cur = *heap.begin();
        heap.erase(heap.begin());
        its[cur.second] = heap.end();
        FOR(i, g[cur.second].size()) {
            int v = g[cur.second][i];
            if (its[v] == heap.end())
                continue;
            int oldDeg = its[v]->first;
            heap.erase(its[v]);
            its[v] = heap.insert(mp(oldDeg-1,v)).first;
        }
    }

    for(set<pair<int,int> >::iterator it = heap.begin(); it!=heap.end();++it) {
        good[it->second]=true;
    }

    int bestval = 0;
    int bestindex = 0;
    FOR(i,n) {
        if (visited[i]>0)
            continue;
        if (!good[i])
            continue;
        stack<int> q;
        q.push(i);
        visited[i] = i+1;
        int counter=1;
        while (q.size()>0) {
            int act = q.top();
            q.pop();
            FOR(j,g[act].size()) {
                int v = g[act][j];
                if (!good[v])
                    continue;
                if (visited[v] >0)
                    continue;
                visited[v] = i+1;
                q.push(v);
                counter++;
            }
        }
        if (counter>bestval) {
            bestval = counter;
            bestindex = i+1;
        }
    }
    if (bestval == 0) {
        printf("NIE\n");
    }else {
        printf("%d\n", bestval);
        FOR(i,n) {
            if (visited[i] == bestindex) {
                printf("%d ", i+1);
            }
        }
        printf("\n");
    }
    return 0;
}