7449번 - The mysterious X network 다국어

One of the reasons for which École polytechnique (nicknamed “X” for reasons to be explained during the debriefing talk) is so deeply rooted in French society is its famous network of camarades — former students of the same school. When one camarade wants something (money, job, etc.), he can ask this network for help and support. In practice, this means that when he/she wants to reach some other camarade, not always of the same year, then surely he can find intermediate camarades to get to her/him. Note that the “camarade” relationship is symmetric. Due to the magic of the X network, there is always a means to reach anybody.

The program you have to write is supposed to help to minimize the number of these intermediate camarades.

The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.

The huge file of all living camarades is simplified so as to obey the following format. The first line in the file is the number of camarades, say N, an integer 1 ≤ N ≤ 10⁵. Camarades are labeled from 0 to N − 1. Follow N lines. Each line starts with the camarade label c, followed by the number of other camarades he/she knows, say nc, followed by the labels of those nc camarades. All these integers are separated by a single blank. It is assumed that nc is always less than 100. The last line in the file is the label of the camarade seeking help (say c₁) followed by the label of the camarade he wants help from, say c₂ (c₂ ≠ c₁).

For each test case, your program should output three integers separated by a blank: c₁, c₂ and the minimal number of intermediate camarades to reach c₂.

The outputs of two consecutive cases will be separated by a blank line.