Problem B
Family DAG

In a perfect world, your family tree would form a complete binary tree, with you at the root. You would have two different parents who were distinct from yourself. You would have four distinct grandparents who were distinct from your parents and yourself, and so on.

Of course, the realities of both rural and royal life may yield a family tree that has the same cast of characters showing up over and over. If we admit the possibility of time travel and its associated paradoxes, it might be possible for a person to return to the past and become their own ancestor (Futurama, season 4, episode 1). Your job is to detect and flag individuals exhibiting these types of aberrant sets of ancestors.

Input

Input consists of up to $100$ family descriptions. Each family is described as a set of at most $100$ parent-child relations, one line per relation, where each is given as parent begat child. The parent and child names are both non-empty sequences of at most $10$ letters from the set A - Z (lower or uppercase). Family descriptions are separated by a single line containing the word done. Input ends at end of file.

If the same name shows up more than once in a family, it is referring to the same person. Each person in a family has at most two parents.

Output

For each family, report in lexicographic order (upper-case characters sort earlier than lower-case characters) all individuals who have either the same person more than once among their ancestors (known as hillbillies) or who show up as ancestors of themselves (known as paradoxes). Note that being a paradox automatically implies you are a hillbilly. Leave a blank line between the reports for different families.

Sally begat Fran
Fran begat Billy
Jethro begat Fran
Jethro begat Milton
Sue begat Milton
Milton begat Billy
done
Alice begat Bob
Eve begat Alice
Bob begat Alice
done

Billy hillbilly

Alice paradox
Bob paradox