import java.text.DecimalFormat;
import java.text.DecimalFormatSymbols;
import java.util.Locale;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;
import java.util.TreeSet;

public class Kcores {
	
	static final int MAXNODE = 1000;

	/**
	 * Reduce g to its k-cores.
	 * 
	 * @param g - the graph
	 * @param k - value of the core
	 */
	static public void kcore(Graph g, int k) {
		boolean changed = true;
out:	do {
			changed = false;
			for (String v : g.vertices()) {
				if (g.degree(v) < k) {
					g.removeNode(v);
					changed = true;
					// have to break b/c we are changing the list
					continue out;
				}
			}
		} while(changed);
	}
	
	static public String kcoreElems(String [][] entries, int numEntries, String u) {
		
		Graph g = new Graph();
		g.readGraph(entries, numEntries);
		
		String result = u + " ";
		
		// kcore the graph
		// XXX: this could be done faster via binary search
		Graph Gk = null;
		int k = 0;
		for(k = g.degree(u); k >= 1; k--) {
			Gk = g.clone();
			kcore(Gk, k);
			if(Gk.contains(u)) break;
		}
		
		TreeSet<String> core = new TreeSet<String>();
		
		if (Gk != null) {
			// compute everything that is in the component
			// (union of BFS levels)
			Map<Integer, Set<String>> levels = Gk.getBFSLevels(u);
			Set<String> Reachable = new TreeSet<String>();
			for(Set<String> L : levels.values()) {
				Reachable.addAll(L);
			}
		
			// output everything in the component
			result = result + k + " ";
			for(String x : Reachable) {
				result = result + x + " ";
			}
		} 
		return result;
	}

	static public void printEntries(String [][] entries, int numEntries) {
		for (int i = 0; i < numEntries; i++) {
			String node1 = entries[i][0];
			
			System.out.print("Node " + node1 + "  neighbors =");
			
			int j = 1;
			while (entries[i][j] != null) {
				String node2 = entries[i][j];
				System.out.print(" " + node2);
				j++;
			}

			System.out.println();
		}
	}
	
	static public void main(String [] args) {
		DecimalFormat fm1 = new DecimalFormat("######",
				new DecimalFormatSymbols(Locale.US));

		// read the graph
		Scanner inp = new Scanner(System.in);

		try {
			String line = inp.nextLine();
			if (!line.equals("GRAPH BEGIN"))
				throw new Exception();
			while (inp.hasNext()) {
				if (!inp.hasNext()) throw new Exception();

				// found new graph
				String [][] entries = new String [MAXNODE][];
				int numEntries = 0;

				while (inp.hasNext()) {
					String ln = inp.nextLine();
					if (ln.equals("GRAPH END")) 	//* end of graph specification
						break;

					String [] entry = new String[MAXNODE];
					int idx = 0;
					
					// read in entry (on single line)
					Scanner sc = new Scanner(ln);
					if(!sc.hasNext()) throw new Exception();
					entry[idx++] = sc.next();		// node

					while (sc.hasNext()) {
						entry[idx++] = sc.next();	// neighbors
					}

					entry[idx] = null;
					entries[numEntries++] = entry;	// save entry 
				}

				// printEntries(entries, numEntries);
				
				// process lines after graph, if any
				while (inp.hasNext()) {
					line = inp.nextLine();
					if (line.equals("GRAPH BEGIN")) {
						break;
					}
					Scanner s = new Scanner(line);
					String src = s.next(); // start node
					
					String core = kcoreElems(entries, numEntries, src);
					System.out.println(core);

				}
			}
		} catch(Exception e) {
			System.out.println("BAD INPUT FORMAT");
		}
	}

}