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
#include <iostream>
#include <climits>
#include <vector>
#include <queue>

using namespace std;

struct Node {

    int visitedBy;

    int id;
    bool meetsCondition;
    int numberOfConnections;
    vector <Node*> connections;

    Node(int i){
        id = i;
    }

};

Node* nodes[200000];
bool visited[200000];

int dfs(int current, int visitedBy){
    visited[current] = true;
    nodes[current]->visitedBy = visitedBy;

    int sum = 1;

    for(int x=0; x<nodes[current]->connections.size(); x++){
        if(nodes[current]->connections[x]->meetsCondition && !visited[nodes[current]->connections[x]->id]){
            sum += dfs(nodes[current]->connections[x]->id, visitedBy);
        }
    }

    return sum;
}

int main() {

    int n, c, d;
    cin >> n >> c >> d;

    for(int x=0; x<n; x++){
        nodes[x] = new Node(x);
        nodes[x]->meetsCondition = true;

        visited[x] = false;
    }

    for(int x=0; x<c; x++){
        int f, t;
        cin >> f >> t;

        nodes[f-1]->connections.push_back(nodes[t-1]);
        nodes[t-1]->connections.push_back(nodes[f-1]);
    }

    for(int x=0; x<n; x++){
        nodes[x]->numberOfConnections = nodes[x]->connections.size();
        nodes[x]->meetsCondition = true;
    }

    queue<Node*> kol;

    for(int x=0; x<n; x++){
        if(nodes[x]->numberOfConnections < d){
            nodes[x]->meetsCondition = false;
            for(int y=0; y<nodes[x]->connections.size(); y++){
                nodes[x]->connections[y]->numberOfConnections--;
                kol.push(nodes[x]);
            }
        }
    }

    while(!kol.empty()){
        Node* tmp = kol.front();
        kol.pop();

        if(tmp->meetsCondition){
            if(tmp->numberOfConnections < d){
                tmp->meetsCondition = false;
                for(int x=0; x<tmp->connections.size(); x++){
                    tmp->connections[x]->numberOfConnections--;
                    kol.push(tmp->connections[x]);
                }
            }
        }
    }

    int maxVisited = 0;
    int maxIndex = -1;

    for(int x=0; x<n; x++){
        if(nodes[x]->meetsCondition && !visited[nodes[x]->id]){
            int current = dfs(x, x);

            if(current > maxVisited){
                maxIndex = x;
                maxVisited = current;
            }
        }
    }
    if(maxIndex == -1){
        cout << "NIE\n";
    } else {
        cout << maxVisited << "\n";

        for(int x=0; x<n; x++){
            if(nodes[x]->visitedBy == maxIndex){
                cout << x+1 << " ";
            }
        }
    }


}