1. 


/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, WS09
* Problem: 10044 - Erdos Numbers
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=12&page=show_problem&problem=985
*
* @author Dennis Wilfert
* @version 1.0, 10/22/2009
*
* Method : BFS
* Status : Accepted
* Runtime: 1.068
*/
import java.io.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.HashMap;
import java.util.StringTokenizer;

class Main {

public static void main(String[] args) throws IOException {

BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
PrintWriter writer = new PrintWriter(new BufferedOutputStream(System.out));

// HashMap zum Speichern der Knoten in verbindung mit den Namen
HashMap<String, Node> table = new HashMap<String, Node>();

StringTokenizer token;
int p, n, i, j, k, length, start, end, nodes;
Node u, v, head;
Edge e;
Node[] queue;
String[] line;
String name;

// Anzahl der Szenarios
int scenarios = Integer.parseInt(reader.readLine()) + 1;

for (i = 1; i < scenarios; i++) {
token = new StringTokenizer(reader.readLine());
// Anzahl der Publikationen
p = Integer.parseInt(token.nextToken());
// Anzahl der Namen, dessen Erdös Number berechnet werden soll
n = Integer.parseInt(token.nextToken());

table.clear();
head = new Node();
// Anzahl der Knoten
nodes = 1;
table.put("Erdos, P.", head);

// Namen zu den Publikationen auslesen und zum Graphen hinzufügen
for (j = 0; j < p; j++) {
u = new Node();
nodes++;
line = (reader.readLine().split(":"))[0].split(",");
length = (line.length / 2) * 2;

// Namen zu einer Publikation auslesen und zum Graphen hinzufügen
for (k = 0; k < length; k += 2) {
// Namen richtig formatieren
name = line[k].trim() + "," + line[k + 1];
v = table.get(name);
// Existiert der Name noch nicht wird er neu hinzugefügt
if (v == null) {
v = new Node();
nodes++;
table.put(name, v);
}
u.addEdge(v);
v.addEdge(u);
}
}

// Graphen durchsuchen um die Erdös Number für jeden Namen zu bestimmen.
head.setDistance(0);
queue = new Node[nodes];
start = 0;
end = 1;
queue[0] = head;
while (start < end) {
u = queue[start++];
e = u.getEdge();
while (e != null) {
v = e.getNode();
if (v.getDistance() == -1) {
v.setDistance(u.getDistance() + 1);
queue[end++] = v;
}
e = e.getNext();
}
}

// Ausgabe Schreiben
writer.println("Scenario " + i);
for (j = 0; j < n; j++) {
// Namen lesen, dessen Erdös Number ausgegeben werden sollen
name = reader.readLine().trim();
k = -1;
u = table.get(name);
if (u != null) {
k = u.getDistance();
}
writer.print(name);
writer.println((k == -1) ? " infinity" : " " + (k / 2));
}
}
writer.flush();
}
}

/**
* Die Knoten des Graphen
*
*/
class Node {

private Edge edge;
private int distance;

public void addEdge(Node v) {
edge = new Edge(v, edge);
distance = -1;
}

public Edge getEdge() {
return edge;
}

public void setDistance(int dist) {
this.distance = dist;
}

public int getDistance() {
return distance;
}
}

/**
* Die Kanten des Graphen
*
*/
class Edge {

private final Node node;
private final Edge next;

public Edge(Node node, Edge next) {
this.node = node;
this.next = next;
}

public Node getNode() {
return node;
}

public Edge getNext() {
return next;
}
}