P2814 Genealogy

People today are increasingly interested in their own family lineage.

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

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.

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.

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