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
import java.util.*;

import static java.lang.Integer.parseInt;

public class mis {

    static int cityCount;
    static int roadCount;
    static int dFactor;

    static Set<Integer>[] cities;

    static int[] result;

    static Queue<Integer> citiesToCheck = new LinkedList<>();

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        String[] firstLine = scanner.nextLine().split(" ");
        cityCount = parseInt(firstLine[0]);
        roadCount = parseInt(firstLine[1]);
        dFactor = parseInt(firstLine[2]);

        cities = new Set[cityCount + 1];
        result = new int[cityCount + 1];

        for (int i = 1; i <= cityCount; i++) {
            cities[i] = new HashSet<>();
            result[i] = -1;
        }

        for (int i = 0; i < roadCount; i++) {
            String[] line = scanner.nextLine().split(" ");
            addRoad(parseInt(line[0]), parseInt(line[1]));
        }

        for (int cityA = 1; cityA <= cityCount; cityA++) {
            removeUselessCities(cityA);
        }

        while (!citiesToCheck.isEmpty()) {
            removeUselessCities(citiesToCheck.poll());
        }

        int indicator = 0;
        int resultSize = 0;

        for (int city = 1; city <= cityCount; city++) {
            Set<Integer> roadsOfCity = cities[city];

            if (roadsOfCity != null && result[city] != indicator) {
                int newIndicator = city;
                int newResultSize = 0;
                result[city] = newIndicator;
                newResultSize++;
                newResultSize += addRoadsToResult(newIndicator, roadsOfCity);
                cities[city] = null;
                if (newResultSize > resultSize) {
                    indicator = newIndicator;
                    resultSize = newResultSize;
                }
            }
        }

        if (resultSize == 0) {
            System.out.println("NIE");
            return;
        }

        System.out.println(resultSize);
        for (int i = 1; i <= cityCount; i++) {
            if (result[i] == indicator) {
                System.out.print(i);
                System.out.print(" ");
            }
        }
        System.out.println();
    }

    private static void removeUselessCities(int cityA) {
        if (cities[cityA] == null)
            return;

        Set<Integer> roadsOfCityA = cities[cityA];
        if (roadsOfCityA.size() < dFactor) {
            Iterator<Integer> iterator = roadsOfCityA.iterator();

            while (iterator.hasNext()) {
                int cityB = iterator.next();
                Set<Integer> roadsOfCityB = cities[cityB];
                roadsOfCityB.remove(cityA);
                iterator.remove();
                if (roadsOfCityB.size() < dFactor) {
                    citiesToCheck.add(cityB);
                }
            }
            cities[cityA] = null;
        }
    }

    private static int addRoadsToResult(int indicator, Set<Integer> roadsOfCityA) {
        int resultSize = 0;
        for (int cityB : roadsOfCityA) {
            if (result[cityB] != indicator) {
                result[cityB] = indicator;
                resultSize++;
                resultSize += addRoadsToResult(indicator, cities[cityB]);
            }
        }
        return resultSize;
    }

    static void addRoad(int cityA, int cityB) {
        cities[cityA].add(cityB);
        cities[cityB].add(cityA);
    }
}