A16352 | Doremy's Swapping Trees

Consider two undirected graphs $G_1$ and $G_2$ . Every node in $G_1$ and in $G_2$ has a label. Doremy calls $G_1$ and $G_2$ similar if and only if:

- The labels in $G_1$ are distinct, and the labels in $G_2$ are distinct.
- The set $S$ of labels in $G_1$ coincides with the set of labels in $G_2$ .
- For every pair of two distinct labels $u$ and $v$ in $S$ , the corresponding nodes are in the same connected component in $G_1$ if and only if they are in the same connected component in $G_2$ .

Now Doremy gives you two trees $T_1$ and $T_2$ with $n$ nodes, labeled from $1$ to $n$ . You can do the following operation any number of times:

- Choose an edge set $E_1$ from $T_1$ and an edge set $E_2$ from $T_2$ , such that $\overline{E_1}$ and $\overline{E_2}$ are similar. Here $\overline{E}$ represents the graph which is given by only reserving the edge set $E$ from $T$ (i.e., the edge-induced subgraph). In other words, $\overline{E}$ is obtained from $T$ by removing all edges not included in $E$ and further removing all isolated vertices.
- Swap the edge set $E_1$ in $T_1$ with the edge set $E_2$ in $T_2$ .

Now Doremy is wondering how many distinct $T_1$ you can get after any number of operations. Can you help her find the answer? Output the answer modulo $10^9+7$ .

The input consists of multiple test cases. The first line contains a single integer $t$ ( $1\le t\le 2\cdot 10^4$ ) — the number of test cases. The description of the test cases follows.

The first line contains an integer $n$ ( $2\le n\le 10^5$ ) — the number of nodes in the trees $T_1$ and $T_2$ .

Each of the following $n-1$ lines contain two integers $u,v$ ( $1\le u,v\le n$ ), representing an undirected edge in $T_1$ . It is guaranteed these edges form a tree.

Each of the following $n-1$ lines contain two integers $u,v$ ( $1\le u,v\le n$ ), representing an undirected edge in $T_2$ . It is guaranteed these edges form a tree.

It is guaranteed that the sum of $n$ does not exceed $2\cdot 10^5$ .

For each test case, you should output a single line with an integer, representing the number of distinct $T_1$ after any number of operations, modulo $10^9+7$ .