Find the Lowest Common Manager

You are given a company hierarchy where each employee has a unique employee ID and a manager. The CEO's manager is represented by ( -1 ). Given two employee IDs, your task is to find the lowest common manager (LCM) of these two employees. The LCM is defined as the deepest (i.e., lowest-level) node in the hierarchy that is an ancestor of both employees.

For example, consider the hierarchy below:

• Employee 1 is the CEO (manager = -1)
• Employees 2 and 3 report to 1
• Employees 4 and 5 report to 2
• Employee 6 reports to 3

If you are asked to find the LCM for employees 4 and 5, the answer is 2.

Solve this problem by reading input from stdin and writing the result to stdout.

inputFormat

The first line contains an integer ( n ) representing the number of employees. The next ( n ) lines each contain two integers ( e_i ) and ( m_i ) where ( e_i ) is an employee ID and ( m_i ) is the manager ID (with ( -1 ) indicating the CEO). The last line contains two integers ( x ) and ( y ), representing the two employees for whom you need to find the lowest common manager.

outputFormat

Output a single integer representing the lowest common manager's employee ID.## sample

6
1 -1
2 1
3 1
4 2
5 2
6 3
4 5

2