Lowest Common Ancestor in Binary Tree

You are given a binary tree with N nodes. The tree is described by N pairs, each representing the left and right child (using 1-indexed node numbers) of the corresponding node. A value of 0 indicates that the child is missing. Additionally, you are given two nodes p and q. Your task is to find the lowest common ancestor (LCA) of these two nodes.

The lowest common ancestor (LCA) of two nodes \(p\) and \(q\) in a binary tree is defined as the deepest node that has both \(p\) and \(q\) as descendants (a node can be a descendant of itself). Formally, if we denote the LCA of \(p\) and \(q\) as \(\text{LCA}(p,q)\), then it satisfies:

[ \text{LCA}(p,q) = \max { d(x) : x \text{ is an ancestor of both } p \text{ and } q }. ]

It is guaranteed that both p and q exist in the tree.

inputFormat

The input is given via standard input in the following format:

N
L1 R1
L2 R2
...
LN RN
p q

Here:

• N is the number of nodes in the tree.
• Each of the next N lines contains two integers Li and Ri representing the left and right children of the i-th node. A value of 0 indicates a missing child.
• The last line contains two integers p and q, the nodes for which you need to find the LCA.

outputFormat

Output a single integer denoting the value of the lowest common ancestor of nodes p and q.

## sample

5
2 3
4 5
0 0
0 0
0 0
4 5

2