Description

Please note that the time limit for this problem is 5s!

Explorer A and Explorer B need to use light bulbs to light up this forest.

There are $n$ light bulbs, numbered $1, 2, \cdots, n$. Explorer A uses $n - 1$ red ropes to connect them into a tree, and Explorer B uses $n - 1$ blue ropes to connect them into another tree.

At the beginning, all bulbs are off. Now we want to turn on some of the bulbs. Explorer A likes connected components, and Explorer B likes paths. They want to know: how many ways are there to turn on bulbs such that the turned-on bulbs form a connected component in A's tree, and form a path in B's tree?

Input Format

The first line contains an integer $T$, meaning there are $T$ test cases. For each test case:

The first line contains an integer $n$.

Lines $2$ to $n$, i.e. line $i + 1$, contain two integers $a_i, b_i$, representing an edge in A's tree.

Lines $n + 1$ to $2n - 1$, i.e. line $i + n$, contain two integers $c_i, d_i$, representing an edge in B's tree.

Output Format

Output $T$ lines. The $i$-th line is the answer for the $i$-th test case.

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

5
9
14

Hint

Sample Explanation:

Diagrams for the three test cases:

Sample 1:

Sample 2:

Sample 3:

For the first test case, the valid sets of bulbs to turn on are:

• $\{1\}$;
• $\{2\}$;
• $\{3\}$;
• $\{1, 2\}$;
• $\{1, 2, 3\}$.

Note that you cannot turn on the set $\{1, 3\}$, because bulbs $1$ and $3$ do not form a connected component in A's tree. You also cannot turn on the set $\{2, 3\}$, because bulbs $2$ and $3$ do not form a path in B's tree.

For the second test case, the valid sets of bulbs to turn on that contain at least two bulbs are:

• $\{1, 2\}$;
• $\{1, 2, 3\}$;
• $\{1, 2, 3, 4\}$;
• $\{1, 2, 3, 4, 5\}$.

Clearly, all bulb sets of size $1$ are valid, so the answer is $4 + 5 = 9$.

Constraints and Notes:

For $20\%$ of the testdata, $n \le 50$, and it satisfies the special constraint $X$.
For $40\%$ of the testdata, $n \le 3000$, and it satisfies the special constraint $X$.
For $70\%$ of the testdata, it satisfies the special constraint $X$.
For $100\%$ of the testdata, $T = 3, 1 \le n \le 10^5$.

Special constraint $X$: $c_i = i, d_i = i + 1$, that is, B's tree is a path, and there is an edge between nodes with adjacent indices.

Translated by ChatGPT 5