CF891D.Sloth

Sloth is bad, mkay? So we decided to prepare a problem to punish lazy guys.

You are given a tree, you should count the number of ways to remove an edge from it and then add an edge to it such that the final graph is a tree and has a perfect matching. Two ways of this operation are considered different if their removed edges or their added edges aren't the same. The removed edge and the added edge can be equal.

A perfect matching is a subset of edges such that each vertex is an endpoint of exactly one of these edges.

树懒很糟糕，明白吗？因此我们决定设计一道题目来惩罚懒惰的人。

你将得到一棵树，你需要计算有多少种方法：先从中移除一条边，再添加一条边，使得最终的图仍是一棵树，并且具有完美匹配。如果两种操作所移除的边不同，或所添加的边不同，则认为这两种操作是不同的。注意：被移除的边与被添加的边可以是同一条边。

完美匹配是指边的一个子集，使得图中每个顶点恰好是该子集中某一条边的一个端点。

The first line contains n (2 ≤ n ≤ 5·105) — the number of vertices.

Each of the next n - 1 lines contains two integers a and b (1 ≤ a, b ≤ n) — the endpoints of one edge. It's guaranteed that the graph is a tree.

第一行包含一个整数 $n$（$2 \leq n \leq 5 \cdot 10^5$）——顶点的数量。

接下来的 $n-1$ 行，每行包含两个整数 $a$ 和 $b$（$1 \leq a, b \leq n$）——一条边的两个端点。保证该图是一棵树。

Output a single integer — the answer to the problem.

输出一个整数——该问题的答案。

In first sample, there are 8 ways:

• edge between 2 and 3 turns to edge between 1 and 3,
• edge between 2 and 3 turns to edge between 1 and 4,
• edge between 2 and 3 turns to edge between 2 and 3,
• edge between 2 and 3 turns to edge between 2 and 4,
• edge between 1 and 2 turns to edge between 1 and 2,
• edge between 1 and 2 turns to edge between 1 and 4,
• edge between 3 and 4 turns to edge between 1 and 4,
• edge between 3 and 4 turns to edge between 3 and 4.

在第一个样例中，共有 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 的边。