Lowest Common Ancestor in Employee Hierarchy

Given a company hierarchy represented by employee reporting relationships, find the Lowest Common Ancestor (LCA) for two given employees. The LCA is defined as the lowest employee in the hierarchy who is an ancestor of both employees. If one or both of the specified employees are not present in the hierarchy, output -1.

The hierarchy is provided as a list of pairs, where each pair (child, parent) indicates that the child employee directly reports to the parent employee. You are to implement a solution that reads the hierarchy from standard input, along with the two employee IDs, and then outputs the LCA to standard output. Note that if the two given employee IDs are the same, the LCA is that employee itself.

Note on formulas: In the explanation, if you need to refer to any formula, please use LaTeX format. For example, the common ancestor can be described as the intersection of the ancestor sets, \(A \cap B\), where \(A\) and \(B\) are the sets of ancestors for the two given employees.

inputFormat

The input is read from standard input (stdin). The first line contains an integer \(n\), the number of reporting relationships. Each of the next \(n\) lines contains two integers separated by a space, representing a child and its parent. The final line contains two integers separated by a space, representing the two employee IDs, \(emp1\) and \(emp2\), for which you must find the LCA.

For example:

4
5 3
3 2
2 1
4 3
5 4

outputFormat

Output a single integer on standard output (stdout). This integer represents the Employee ID of the Lowest Common Ancestor. If one or both employees are not present in the hierarchy, output -1.

## sample

4
5 3
3 2
2 1
4 3
5 4

3

</p>