Common Manager Finder

You are given a set of employee-manager relationships in the form of strings. Each string represents an association in the format Employee -> Manager, where Manager can be None to denote that the employee is at the top of the hierarchy (e.g. the CEO).

For two given employees, your task is to determine their lowest common manager. In other words, consider the chain (or hierarchy) of managers starting from an employee and moving up to the CEO. Formally, for an employee e, the hierarchy chain P(e) is defined as:

\(P(e): e, \text{manager}(e), \text{manager}(\text{manager}(e)), \ldots \text{ until } 'None'\)

The lowest common manager is the last common element in the paths of the two employees when these paths are aligned from the CEO (or top of the hierarchy) downward.

inputFormat

The input is given via standard input (stdin) and has the following format:

1. An integer N representing the number of employee-manager relationship records.
2. N lines, each containing a relationship in the format Employee -> Manager. The Manager can be None if the employee is at the top of the hierarchy.
3. One line containing the first employee's name (emp1).
4. One line containing the second employee's name (emp2).

outputFormat

Output via standard output (stdout) a single line containing the common manager's name for the two given employees.

## sample

7
CEO -> None
Alice -> Bob
Bob -> Martin
Sophie -> Alice
Martin -> None
Jake -> Sophie
Edward -> Sophie
Alice
Jake

Alice

</p>