题目描述

给你一棵包含$n$个节点的树。 匹配一组边，其中每个节点最多是其中一条边的端点。匹配中最多有多少条边？

输入

第一行输入包含一个整数$n$：节点的数量。节点编号为$1, 2, …, n$。然后有$n-1$行描述边。每行包含两个整数$a$和$b$：节点$a$和节点$b$之间有一条边。

输出

输出一个整数：最大边组数。

输入样例

5
1 2
1 3
3 4
3 5

输出样例

2

提示

样例解释：一个可能的匹配是 ($1, 2$) 和 ($3, 4$)。 数据范围： $1≤n≤2⋅10^5$ $1≤a,b≤n$

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共10个测试点，非原站或官方原始数据。总分100分。