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 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.HashMap; import java.util.HashSet; import java.util.LinkedList; import java.util.List; import java.util.Map; import java.util.StringTokenizer; import java.util.TreeMap; import java.util.TreeSet; public class mis { public static void main(String[] args) throws IOException { BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer tokenizer; tokenizer = new StringTokenizer(reader.readLine()); int n = Integer.parseInt(tokenizer.nextToken()); int m = Integer.parseInt(tokenizer.nextToken()); int d = Integer.parseInt(tokenizer.nextToken()); TreeMap> roads = new TreeMap>(); for(int i = 1; i <= n; i++) { roads.put(i, new HashSet()); } for(int i = 0; i < m; i++) { tokenizer = new StringTokenizer(reader.readLine()); int a = Integer.parseInt(tokenizer.nextToken()); int b = Integer.parseInt(tokenizer.nextToken()); roads.get(a).add(b); roads.get(b).add(a); } LinkedList nuclearHolocaust = new LinkedList(); for(int i = 1; i <= n; i++) { if(roads.get(i).size() < d) { nuclearHolocaust.add(i); } } while(!nuclearHolocaust.isEmpty()) { Integer city = nuclearHolocaust.pop(); HashSet neighbours = roads.remove(city); for(Integer neighbour : neighbours) { roads.get(neighbour).remove(city); if(roads.get(neighbour).size() == d - 1) { nuclearHolocaust.add(neighbour); } } } // System.out.println("size=" + roads.size()); TreeSet best = new TreeSet(); while(!roads.isEmpty()) { TreeSet current = new TreeSet(); LinkedList neighbours = new LinkedList(); Integer roadsPop = roads.firstKey(); neighbours.add(roadsPop); while(!neighbours.isEmpty()) { Integer neighbour = neighbours.pop(); if(roads.get(neighbour) != null) { current.add(neighbour); neighbours.addAll(roads.get(neighbour)); roads.remove(neighbour); } } if(best.size() < current.size()) { best = current; } } if(best.isEmpty()) { System.out.println("NIE"); } else { System.out.println(best.size()); StringBuilder sb = new StringBuilder(); boolean emptySb = true; for(Integer city : best) { if(!emptySb) { sb.append(" "); } sb.append(city); emptySb = false; } System.out.println(sb.toString()); } } }