Max LCA Sum

 MoEngage has given you two trees $T_1$ and $T_2$. Both trees have $N$ nodes and are rooted at node $1$.

Definitions:

• $LCA_1(u,v) = $ Lowest common ancestor of node $u$ and node $v$ in tree $T_1$.
• $LCA_2(u,v) = $ Lowest common ancestor of node $u$ and node $v$ in tree $T_2$.
• $H_1(v) = $ Number of nodes in the shortest path from node $1$ to node $v$ in tree $T_1$. Note that, $H_1(1) = 1$.
• $H_2(v) = $ Number of nodes in the shortest path from node $1$ to node $v$ in tree $T_2$. Note that, $H_2(1) = 1$.

Find the maximum value of $H_1(LCA_1(u,v)) + H_2(LCA_2(u,v))$ over all pairs $(u,v)$ such that $u \neq v$.

More formally, find $\max\limits_{1 \leq u \lt v \leq N} [H_1(LCA_1(u,v)) + H_2(LCA_2(u,v))]$.

Input Format

• First line will contain $T$, the number of test cases. Then the test cases follow.
• First line of each test case contains a single integer $N$, the number of nodes.
• Each of the next $(N - 1)$ lines contain two integers $u$ and $v$ denoting an edge between nodes $u$ and $v$ in tree $T_1$.
• Each of the next $(N - 1)$ lines contain two integers $u$ and $v$ denoting an edge between nodes $u$ and $v$ in tree $T_2$.

Output Format

For each test case, output in a single line $\max\limits_{1 \leq u \lt v \leq N} [H_1(LCA_1(u,v)) + H_2(LCA_2(u,v))]$.

Constraints

• $1 \leq T \leq 10^4$
• $2 \leq N \leq 10^5$
• Sum of $N$ over all test cases does not exceed $10^5$.

Sample Input 1 

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

Sample Output 1 

5
3

Explanation

• Test case $1$: The trees $T_1$ and $T_2$ are: 

For $u = 3$ and $v=5$, $LCA_1(3,5) = 3$, $LCA_2(3,5) = 3$, $H_1(3) = 2,H_2(3) = 3$. Thus, $H_1(LCA_1(3,5)) + H_2(LCA_2(3,5)) = H_1(3) + H_2(3) = 5$.
It can be proven that $5$ is the maximum possible answer for this case amongst all pairs $(u,v)$.

• Test case $2$: The trees $T_1$ and $T_2$ are: 

For $u = 2$ and $v=4$, $LCA_1(2,4) = 2$, $LCA_2(2,4) = 1$, $H_1(2) = 2,H_2(1) = 1$. Thus, $H_1(LCA_1(2,4)) + H_2(LCA_2(2,4)) = H_1(2) + H_2(1) = 3$.
It can be proven that $3$ is the maximum possible answer for this case amongst all pairs $(u,v)$.