题目描述

给定一颗$n$个节点，$n-1$条边的树，现在Fox想让你为图中的每一点$v$赋值为整数$a_v$。$(1\leq{a_v}\leq3,)$。问有多少种方案，使得：对于每条边$u-v$，$（a_u+a_v）$为奇数。

由于方案数可能很大，对$10^9+7$取模输出。如果没有方案，输出$-1$。

输入格式

第一行输入一个$n$。$（2\leq{n}\leq{10^5}）$ 接下来$n-1$行，每行输入两个数$u,v$，表示$u,v$直接一条无向边。

输出格式

输出一个整数。

样例

3
1 2
1 3

6

来源

2022 HGNU-SWUT暑假联合集训