Description

As stated, given a rooted multi-branch tree, find the lowest common ancestor of the specified two nodes.

Input Format

The first line contains three positive integers $N,M,S$, which denote the number of nodes in the tree, the number of queries, and the index of the root node, respectively.

Each of the next $N-1$ lines contains two positive integers $x, y$, indicating that there is a directly connected edge between node $x$ and node $y$ (the testdata guarantees the edges form a tree).

Each of the next $M$ lines contains two positive integers $a, b$, asking for the lowest common ancestor of node $a$ and node $b$.

Output Format

Output $M$ lines, each containing one positive integer, which are the answers to the queries in order.

5 5 4
3 1
2 4
5 1
1 4
2 4
3 2
3 5
1 2
4 5

4
4
1
4
4

Hint

Constraints:

• For $30\%$ of the testdata, $N\leq 10$, $M\leq 10$.
• For $70\%$ of the testdata, $N\leq 10000$, $M\leq 10000$.
• For $100\%$ of the testdata, $1 \leq N,M\leq 5\times10^5$, $1 \leq x, y,a ,b \leq N$, and it is not guaranteed that $a \neq b$.

Sample explanation:

The tree structure is as follows:

• First query: the lowest common ancestor of $2, 4$ is $4$.
• Second query: the lowest common ancestor of $3, 2$ is $4$.
• Third query: the lowest common ancestor of $3, 5$ is $1$.
• Fourth query: the lowest common ancestor of $1, 2$ is $4$.
• Fifth query: the lowest common ancestor of $4, 5$ is $4$.

Therefore, the outputs are $4, 4, 1, 4, 4$ in order.

2021/10/4 testdata update @fstqwq: Added two more sets of testdata to block brute-force jumping.

Translated by ChatGPT 5