Lowest Common Ancestor in Binary Tree

You are given a binary tree and two node values p and q. Your task is to find the lowest common ancestor (LCA) of the two nodes in the tree.

A binary tree is provided in a specific format: the tree is represented by an integer N which is the number of nodes. Each node in the tree is numbered from 1 to N. For each node, two integers are given representing the left and right child respectively. If a child is missing, its value is -1.

After the tree representation, two integers p and q are provided. You are required to output the value of the lowest common ancestor node of these two nodes.

The lowest common ancestor of two nodes p and q is defined as the lowest node in the tree that has both p and q as descendants (where we allow a node to be a descendant of itself). The LCA problem is a classic one in computer science with numerous applications including file directories and network routing.

inputFormat

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

1. The first line contains an integer T denoting the number of test cases.
2. For each test case:
   • The first line contains an integer N, the number of nodes in the tree.
   • The next N lines each contain two space-separated integers. The i-th of these lines represents the left and right children of node i (using -1 to indicate a null child).
   • The following line contains two space-separated integers p and q, the values of the nodes whose LCA you need to find.

Note: The nodes are indexed starting from 1.

outputFormat

For each test case output via standard output a single line containing the value of the lowest common ancestor node of p and q.

## sample

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

3
1

</p>