CF1889E.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$.

考虑两个无向图 $G_1$ 和 $G_2$。$G_1$ 和 $G_2$ 中的每个节点均有一个标签。Doremy 称 $G_1$ 和 $G_2$ 相似，当且仅当满足以下条件：

• $G_1$ 中所有节点的标签互不相同，且 $G_2$ 中所有节点的标签也互不相同；
• $G_1$ 的标签集合 $S$ 与 $G_2$ 的标签集合完全相同；
• 对于 $S$ 中任意两个不同的标签 $u$ 和 $v$，它们在 $G_1$ 中对应的节点处于同一连通分量，当且仅当它们在 $G_2$ 中对应的节点也处于同一连通分量。

现在 Doremy 给你两棵含 $n$ 个节点的树 $T_1$ 和 $T_2$，节点标签为 $1$ 到 $n$。你可以执行如下操作任意多次：

• 从 $T_1$ 中选取一个边集 $E_1$，从 $T_2$ 中选取一个边集 $E_2$，使得 $\overline{E_1}$ 和 $\overline{E_2}$ 相似。其中 $\overline{E}$ 表示仅保留原树 $T$ 中边集 $E$ 所构成的图（即边导出子图）；换言之，$\overline{E}$ 是从 $T$ 中删去所有不属于 $E$ 的边，并进一步删去所有孤立顶点后所得的图。
• 将 $T_1$ 中的边集 $E_1$ 与 $T_2$ 中的边集 $E_2$ 交换。

现在 Doremy 想知道：经过任意次上述操作后，能获得多少种互不相同的 $T_1$？你能帮她求出答案吗？请将答案对 $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$.

输入包含多个测试用例。第一行包含一个整数 $t$（$1\le t\le 2\cdot 10^4$），表示测试用例的数量。随后是各测试用例的描述。

第一行包含一个整数 $n$（$2\le n\le 10^5$），表示树 $T_1$ 和 $T_2$ 的节点数量。

接下来的 $n-1$ 行中，每行包含两个整数 $u,v$（$1\le u,v\le n$），表示树 $T_1$ 中的一条无向边。保证这些边构成一棵树。

再接下来的 $n-1$ 行中，每行包含两个整数 $u,v$（$1\le u,v\le n$），表示树 $T_2$ 中的一条无向边。保证这些边构成一棵树。

保证所有测试用例的 $n$ 之和不超过 $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$.

对于每个测试用例，你应该输出一行一个整数，表示经过任意次操作后不同的 $T_1$ 的数量，对 $10^9+7$ 取模。

In the first test case, there is at most one distinct $T_1$ having the only edge $(1,2)$.

In the second test case, you can choose the edge set ${(1,3),(2,3)}$ in $T_1$, the edge set ${(1,2),(2,3)}$ in $T_2$ and swap them. So $T_1$ can be $1-3-2$ or $1-2-3$.

In the third test case, there are $4$ distinct $T_1$, as the following pictures.

在第一个测试用例中，至多存在一个不同的 $T_1$，其唯一边为 $(1,2)$。

在第二个测试用例中，你可以在 $T_1$ 中选择边集 ${(1,3),(2,3)}$，在 $T_2$ 中选择边集 ${(1,2),(2,3)}$，并交换它们。因此 $T_1$ 可以是 $1-3-2$ 或 $1-2-3$。

在第三个测试用例中，共有 $4$ 个不同的 $T_1$，如下图所示。