题目描述

一个网络由 \(N\) 台计算机组成 (\(1≤N≤100,000\)，编号\(1 \sim N\))，这些计算机由 \(N-1\) 条通信链路连接，任意两台计算机可以通过唯一的路径来通信。如果两台计算机之间存在直接通信链接，则它们称为相邻计算机。相邻计算机是与之相邻的计算机集。为了快速访问和检索大量信息，我们需要选择一些计算机充当服务器来为其邻居提供资源。请注意，服务器可以为其所有相邻计算机服务。

如果选择的这些服务器可以实现，每个客户端（非服务器）正好由一个服务器提供服务，就可以形成完美的服务。问题是找到构成完美服务的最小服务器数量，我们将此数量称为完美服务数。

格式

输入格式

第一行包含一个正整数 \(N\)，它代表网络中的计算机数量。

接下来的 \(N−1\) 行包含所有通信链接，每个链接包含一行。每行由两个正整数表示，并用一个空格隔开。

输出格式

一个正整数表示完美服务数。

样例1

输入样例1

6 
1 3 
2 3 
3 4 
4 5 
4 6

输出样例1

2

限制

时间：\(1s\) 空间：\(256M\)

对于 \(100\%\) 的数据：\(1≤N≤100,000\)；

来源

地址：\(zloj,J2020\)域
作者：\(jialiang2509\)
模拟赛\(T1\)