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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;

public class mis {

    static class Node {
        final int value;
        final List<Node> edges = new ArrayList<>();

        public Node(int value) {
            this.value = value;
        }

        @Override
        public String toString() {return "" + value;}
    }

    static class Graph {
        int size;
        Node[] nodes;

        public Graph(int size) {
            this.size = size;
            nodes = new Node[size + 1];
            for (int i=1; i<=size; i++) nodes[i] = new Node(i);
        }

        void connect(int a, int b) {
            nodes[a].edges.add(nodes[b]);
            nodes[b].edges.add(nodes[a]);
//            System.out.println("DEBUG: " + a + " size: " + nodes[a].edges.size());
//            System.out.println("DEBUG: " + b + " size: " + nodes[b].edges.size());
        }
    }

    static List<Node> findWeaks(Graph G, int d) {
        List<Node> answer = new ArrayList<>();
        for (int i=1; i<=G.size; i++) {
            if (!G.nodes[i].edges.isEmpty() && G.nodes[i].edges.size() < d) {
                answer.add(G.nodes[i]);
            }
        }
        return answer;
    }

    static void removeWeaks(Graph G, List<Node> toDelete) {
        for (Node x: toDelete) {
            for (Node child: x.edges) {
                child.edges.remove(x);
            }

            x.edges.clear();
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int d = in.nextInt();

        Graph G = new Graph(n);

        for (int i=1; i<=m; i++) {
            G.connect(in.nextInt(), in.nextInt());
        }

//        G.connect(1, 2);
//        G.connect(2, 3);
//        G.connect(3, 4);
//        G.connect(4, 2);

//        for (int i=1; i<=n; i++) {
//            System.out.println(i + " => " + G.nodes[i].edges);
//        }

        while (true) {
            List<Node> weaks = findWeaks(G, d);
//            System.out.println(weaks);
            if (weaks.isEmpty()) {
                break;
            } else {
                removeWeaks(G, weaks);
            }
        }

        List<Integer> maxArray = new ArrayList<>();
        int maxSize = Integer.MIN_VALUE;
        boolean[] visited = new boolean[n + 1];
        for (int i=1; i<=n; i++) {
            if (visited[i] || G.nodes[i].edges.size() < d) continue;
            List<Integer> currentArray = new ArrayList<>();

            Queue<Integer> Q = new ArrayDeque<>();
            Q.add(i);
            int counter = 0;
            while (!Q.isEmpty()) {
                int current = Q.poll();

                if (!visited[current]) {
                    currentArray.add(current);
                    ++counter;
                    visited[current] = true;

                    for (Node child : G.nodes[current].edges) {
                        if (!visited[child.value]) Q.add(child.value);
                    }
                }
            }

            if (maxSize < counter) {
                maxSize = counter;
                maxArray = currentArray;
            }

        }
//        System.out.println(maxSize);

        if (maxSize <= d) System.out.println("NIE");
        else {
            int[] ints = new int[maxSize];

            for (int i=0; i<maxArray.size(); i++) {
                ints[i] = maxArray.get(i);
            }

            Arrays.sort(ints);

            StringBuilder sb = new StringBuilder();
            sb.append(ints[0]);
            for (int i=1; i<maxSize; i++) {
                sb.append(" ");
                sb.append(ints[i]);
            }

            System.out.println(maxSize);
            System.out.println(sb.toString());
        }

    }
}