懒惰是不好的,好吗?所以我们决定准备一个问题来惩罚懒惰的人。
给定一棵树,您应该计算从中删除边的方法的数量,然后向其添加边,以便最终的图是一棵树并且具有完美匹配。如果删除的边或添加的边不相同,则该操作的两种方式被认为是不同的。移除的边和添加的边可以相等。
完美匹配是边的子集,使得每个顶点恰好是这些边之一的端点。
输入
第一行包含 n (2 ≤ n ≤ 5·105) — 顶点数。
接下来的 n - 1 行中的每一行都包含两个整数 a 和 b (1 ≤ a, b ≤ n) — 一条边的端点。保证该图是一棵树。
输出
输出一个整数——问题的答案。
示例
输入 #1
4 1 2 2 3 3 4
输出 #1
8
输入 #2
5 1 2 2 3 3 4 3 5
输出 #2
0
输入 #3
8 1 2 2 3 3 4 1 5 5 6 6 7 1 8
输出 #3
22
注意
在第一个示例中,有 8 种方式:
- 2 和 3 之间的边转向 1 和 3 之间的边,
- 2 和 3 之间的边转向 1 和 4 之间的边,
- 2 和 3 之间的边转向 2 和 3 之间的边,
- 2 和 3 之间的边转向 2 和 4 之间的边,
- 1 和 2 之间的边变成 1 和 2 之间的边,
- 1 和 2 之间的边变成 1 和 4 之间的边,
- 3 和 4 之间的边转向 1 和 4 之间的边,
- 3 和 4 之间的边缘转向 3 和 4 之间的边缘。