Description

Given sufficient father–son relationships, write a program to find a person’s earliest ancestor.

Input Format

The input consists of multiple lines. First comes a series of descriptions of father–son relationships. In each group, the father appears on exactly one line written as #name, and the sons appear on zero or more lines written as +name. After that, lines written as ?name indicate queries asking for that person’s earliest ancestor. Finally, a single $ on its own line marks the end of file.

Output Format

For each query, in the order they appear in the input, output the person’s earliest ancestor in the format: the person’s name $+$ a space $+$ the ancestor’s name $+$ a newline.

#George
+Rodney
#Arthur
+Gareth
+Walter
#Gareth
+Edward
?Edward
?Walter
?Rodney
?Arthur
$

Edward Arthur
Walter Arthur
Rodney George
Arthur Arthur

Hint

Each person’s name has exactly $6$ characters, the first letter is uppercase, and no two people share the same name. There can be at most $10^3$ groups of father–son relationships, the total number of people can be up to $5 \times 10^4$, and the genealogy records do not exceed $30$ generations.

Translated by ChatGPT 5