题目描述

一个网络由$N$台计算机通过$N-1$条通信链路连接而成，任意两台计算机之间都存在唯一的通信路径。如果两台计算机之间有一条通信链路，则称它们是相邻的。一台计算机的邻居是指与它相邻的所有计算机的集合。为了快速访问和检索大量信息，需要选择一些计算机作为服务器，为它们的邻居提供资源。注意，一台服务器可以为其所有邻居提供服务。当网络中的服务器集合满足每个客户端（非服务器）恰好被一台服务器服务时，称该集合形成一个完美服务。我们的目标是找到形成完美服务所需的最小服务器数量，这个数量称为完美服务数。

假设$N$（$\leq 10000$）是正整数，且这$N$台计算机编号为$1$到$N$。例如，图1展示了一个由6台计算机组成的网络，其中黑色节点表示服务器，白色节点表示客户端。在图1(a)中，服务器3和5不构成完美服务，因为客户端4同时与服务器3和5相邻，因此被两台服务器服务，这违反了条件。相反，如图1(b)所示，服务器3和4构成完美服务，且该集合的规模最小。因此，这个例子的完美服务数为2。

你的任务是编写一个程序，计算完美服务数。

输入格式

输入包含多个测试用例。每个测试用例的格式如下：
第一行包含一个正整数$N$，表示网络中的计算机数量。接下来的$N-1$行每行包含两个正整数，表示一条通信链路。第$N+1$行的$0$表示该测试用例结束。
下一个测试用例在前一个测试用例的结束符$0$之后开始。输入以$-1$结束。

输出格式

对每个测试用例，输出一行，包含一个正整数，即完美服务数。

输入数据示例1

6  
1 3  
2 3  
3 4  
4 5  
4 6  
0  
2  
1 2  
-1  

输出数据示例1

2  
1  

来源

高雄 2006