← 返回题目列表

AtCoder · xmascon17_f

F. 树拆卸

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

配点 : 100 点

問題文

拥有圣诞树的蓝色兔子和红色鳗鱼碰在了一起,两棵树纠缠在了一起。


N 给定由顶点组成的图。 顶点具有 1 〜 N 的编号。 边连接 N*2-2 书籍可用,i 第一条边是顶点 A_i 和 边缘 B_i 。

有多少种方法可以将这个图的边涂成红色和蓝色,使得仅由红色边组成的图以及仅由蓝色边组成的图都成为树?

答案可能非常大,所以 计算除以10^9+7 后求余数。

制約

  • 4 \leq N \leq 104
  • 1 \leq A_i,B_i \leq N
  • 不存在自环和多重边
  • 满足问题中条件的涂色方法至少有 1 种以上

採点

测试用例是 01.txt 〜 10.txt 可以得到第 10 个,并且对于测试用例 1 每正确解答 10 积分。

本题的测试用例已公开,单击此处可以从中下载。


入力

输入是按以下格式从标准输入给出的。

N
A_1 B_1
A_2 B_2
:
A_{N*2-2} B_{N*2-2}

出力

答案 请打印除以 10^9+7 除以后的余数输出。


入力例 1

4
1 2
1 3
1 4
2 3
2 4
4 3

出力例 1

12

在这个案例中,有以下 12 种涂色方法。

图:涂色方法一览