题目描述

给定一棵树，其中有 $N$ 个节点。求出满足以下条件的点 $u$ 的数量：

• 把 $u$ 和连接 $u$ 的边全部删除后得到的图的最大匹配与原树的最大匹配相等。

$2\leq N \leq 2\times 10^5$。

输入格式

第一行输入一个整数 $n$

接下来 $n-1$ 行每行两个整数 $u,v$

输出格式

输出答案

3
1 2
2 3

2

2
1 2

0

6
2 5
3 5
1 4
4 5
4 6

4

提示

$2\leq N \leq 2\times 10^5$。