import java.io.File;
import java.text.DecimalFormat;
import java.text.DecimalFormatSymbols;
import java.util.Locale;
import java.util.Map;
import java.util.HashMap;
import java.util.Scanner;
import java.util.Set;

public class LifeConnections {

	static final int MAXNODE = 1000;

	/**
	 * Count the number of shortest paths between u and v in g.
	 * @param g - the graph g
	 * @param u - starting vertex u
	 * @param v - ending vertex v
	 * @return
	 */
	static public long countPaths(String [][] entries, int numEntries, String u, String v) {
		
		Graph g = new Graph();
		g.readGraph(entries, numEntries);
		
		// compute the BFS levels
		Map<Integer, Set<String>> levels = g.getBFSLevels(u);
		int max_levels = 0;
		for(int i : levels.keySet()) max_levels = Math.max(i, max_levels);

		// store the intermediate counts
		Map<String, Long> counts = new HashMap<String, Long>();
		
		// compute the base case
		counts.put(u, 1L);
		
		// for every BFS level
		for(int i = 1; i <= max_levels; i++) {
			
			// for every vertex in the current level
			for(String w : levels.get(i)) {
				
				// sum over its neighbors in the previous level
				long s = 0;
				for(String x : g.getNeighbors(w)) {
					if(levels.get(i-1).contains(x)) {
						s += counts.get(x);
					}
				}
				counts.put(w, s);
				
				// if we've found v, we're done.
				if(w.equals(v)) return s;
			}
		}
		return 0;
	}


	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 dest = s.next(); // end node
					
					long c = countPaths(entries, numEntries, src, dest);
					System.out.println(src + " " + dest + " " + fm1.format(c));

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

}