Find All Ancestors in a Tree

You are given a series of parent-child relationships representing a tree structure. For a given node, your task is to print all its ancestors. An ancestor is defined as any node that appears in the chain of parents from the given node. In other words, if a node n has a parent p, then p is an ancestor of n, and all ancestors of p are also ancestors of n.

Formally, if we denote the direct parent relationship by a function, then the set of ancestors of a node v can be defined by the recursive formula:

$$ A(v) = \begin{cases} \varnothing & \text{if } v \text{ has no parent},\\ \{p\} \cup A(p) & \text{if } p \text{ is the parent of } v. \end{cases} $$

You must read the input from standard input (stdin) and output the result to standard output (stdout). The output should list all ancestors of the given node in lexicographically sorted order, separated by a single space. If there are no ancestors, output an empty line.

inputFormat

The input consists of:

1. A line containing a string representing the target node.
2. A line with an integer N representing the number of parent-child relationships.
3. N subsequent lines, each containing two space-separated strings representing a parent and a child.

You can assume that each child has at most one direct parent.

outputFormat

Output a single line containing all the ancestors of the given node in lexicographically sorted order, separated by a single space. If the node has no ancestors, output an empty line.

child
4
grandparent parent
parent child
grandparent uncle
uncle cousin

grandparent parent