← 返回题目列表

Codeforces · 1889/E

E. 多雷米的交换树

中文机器翻译题面 查看原题

考虑两个无向图 $$$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$$$,如下图所示。