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
#include <stdio.h>
#include <algorithm>
#include <list>
#include <set>
#include <queue>
#include <vector>

using namespace std;

struct Node {
    set<int> next;
    int degree;
    bool visited;

    Node() {
        this->degree = 0;
        this->visited = false;
    }
};

struct DegreeCompare {
    bool operator()(const Node *a, const Node *b) {
        return a->degree == b->degree? a < b : a->degree < b->degree;
    }
};

typedef set<Node*, DegreeCompare> PriorityQueue;

int bfs(Node *graph, int start, vector<int> &nodes) {
    int size = 0;
    queue<int> q;
    q.push(start);
    graph[start].visited = true;
    while(!q.empty()) {
        int node = q.front();
        q.pop();
        nodes.push_back(node);
        ++size;
        for(set<int>::iterator it = graph[node].next.begin(); it != graph[node].next.end(); ++it) {
            if(!graph[*it].visited) {
                graph[*it].visited = true;
                q.push(*it);
            }
        }
    }
    return size;
}

int main() {
    int n, m, d;
    scanf("%d %d %d", &n, &m, &d);
    Node *graph = new Node[n];
    for(int i = 0; i < m; ++i) {
        int a, b;
        scanf("%d %d", &a, &b);
        --a;
        --b;
        graph[a].next.insert(b);
        ++graph[a].degree;
        graph[b].next.insert(a);
        ++graph[b].degree;
    }

    PriorityQueue q;
    for(int i = 0; i < n; ++i) {
        q.insert(graph + i);
    }

    while(!q.empty()) {
        Node *lowest = *q.begin();
        if(lowest->degree >= d) {
            break;
        }

        q.erase(q.begin());
        for(set<int>::iterator it = lowest->next.begin(); it != lowest->next.end(); ++it) {
            Node *next = graph + *it;
            q.erase(next);
            --next->degree;
            next->next.erase(lowest - graph);
            q.insert(next);
        }
    }

    if(q.empty()) {
        printf("NIE");
    } else {
        int bestSize = 0;
        vector<int> nodes, bestNodes;
        for(PriorityQueue::iterator it = q.begin(); it != q.end(); ++it) {
            if(!(*it)->visited) {
                int start = *it - graph;
                nodes.clear();
                int size = bfs(graph, start, nodes);
                if(size > bestSize) {
                    bestSize = size;
                    bestNodes.swap(nodes);
                }
            }
        }

        sort(bestNodes.begin(), bestNodes.end());
        printf("%d\n", bestNodes.size());
        for(vector<int>::iterator it = bestNodes.begin(); it < bestNodes.end(); ++it) {
            printf("%d ", *it + 1);
        }
    }
    printf("\n");

    return 0;
}