配点 : 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 种涂色方法。
图:涂色方法一览