Lowest Common Ancestor in a Rooted Tree

Given a rooted multi-branch tree, your task is to find the lowest common ancestor (LCA) of two specified nodes. The lowest common ancestor of two nodes is defined as the deepest node that is an ancestor of both nodes.

The tree is provided as follows: the first line contains an integer n (the number of nodes). The next n-1 lines each contain two integers u and v indicating that node u is the parent of node v. The last line contains two integers representing the nodes for which you need to determine the LCA. It is guaranteed that the tree is rooted at node 1.

inputFormat

The first line contains an integer n (1 ≤ n ≤ 10⁵), representing the number of nodes in the tree. Each of the next n-1 lines contains two integers u and v (1 ≤ u, v ≤ n) indicating that node u is the parent of node v. The final line contains two integers, representing the two nodes for which the LCA is to be found.

outputFormat

Output a single integer representing the lowest common ancestor of the two given nodes.

sample

5
1 2
1 3
2 4
2 5
4 5

2