问题陈述

给定一棵有 $N$ 个顶点的树。第 $i$ 条边（$1 \leq i \leq N-1$）双向连接顶点 $u_i$ 和 $v_i$。

向给定的树中添加一条无向边，总是会得到一个恰好含有一个环的图。

在这些图中，有多少个满足以下所有条件？

• 该图是简单图。
• 环上的所有顶点的度数均为 $3$。

约束

• $3 \leq N \leq 2 \times 10^5$
• $1 \leq u_i, v_i \leq N$
• 给定的图是一棵树。
• 所有输入值均为整数。

输入

输入从标准输入按以下格式给出：

$N$ $u_1 v_1$ $u_2 v_2$ $\vdots$ $u_{N-1} v_{N-1}$

输出

输出答案。

样例输入 1

6
1 2
2 3
3 4
4 5
3 6

样例输出 1

1

添加一条连接顶点 $2$ 和 $4$ 的边会得到一个简单图，其中环上的所有顶点度数均为 $3$，因此它满足条件。

样例输入 2

7
1 2
2 7
3 5
7 3
6 2
4 7

样例输出 2

0

有些情况下不存在满足条件的图。

样例输入 3

15
1 15
11 14
2 10
1 7
9 8
6 9
4 12
14 5
4 9
8 11
7 4
1 13
3 6
11 10

样例输出 3

6