考虑两个无向图 $$$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 为您提供了两棵树 $$$T_1$$$ 和 $$$T_2$$$,具有 $$$n$$$ 节点,标记为从 $$$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$$$ 取模的答案。
输入
输入由多个测试用例组成。第一行包含一个整数 $$$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$$$。
输出
对于每个测试用例,您应该输出一个带有整数的单行,表示任意次数操作后不同 $$$T_1$$$ 的数量,以 $$$10^9+7$$$ 为模。
示例
输入 #1
3 2 1 2 2 1 3 1 3 2 3 2 3 2 1 4 1 2 2 3 3 4 4 2 2 1 1 3
输出 #1
1 2 4
注意
在第一个测试用例中,最多有一个不同的 $$$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$$$,如下图所示。