← 返回题目列表

Codeforces · 251/E

E. 树和表

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

小Petya非常喜欢树。最近,他的母亲送给他一棵有 2n 个节点的树。 Petya立即决定将这棵树放在一个由2行n列组成的矩形桌子上,以满足以下条件:

1. 表的每个单元格恰好对应一个树节点,反之亦然,每个树节点恰好对应一个表单元格。
2. 如果两个树节点通过边连接,则相应的单元具有公共边。

现在 Petya 想知道有多少种方法可以把他的树放在桌子上。如果存在一个树节点对应于这两个放置中不同的表单元格,则他将这两个放置称为不同的放置。由于大数字可能会吓到 Petya,因此请打印对 1000000007 (109 + 7) 取模的答案。

输入

第一行包含一个整数 n (1 ≤ n ≤ 105)。接下来 (2n - 1) 行包含两个整数,每个 ai 和 bi (1 ≤ ai, bi ≤ 2n; ai ≠ bi),它们确定由相应边连接的顶点的数量。

考虑用 1 到 2n 的整数编号的树顶点。保证输入中给出的图是一棵树,即连通的无环无向图。

输出

打印一个整数 — 将树放置在表上所需的方式数以 1000000007 (109 + 7) 为模。

示例

输入 #1

3
1 3
2 3
4 3
5 1
6 2

输出 #1

12

输入 #2

4
1 2
2 3
3 4
4 5
5 6
6 7
7 8

输出 #2

28

输入 #3

2
1 2
3 2
4 2

输出 #3

0

注意

第一个示例的注释(下面给出了将树放置在桌子上的所有 12 种变体):