2448. [UVa 1218]完美的服务

【题目描述】

网络由$n$台计算机组成，这些计算机通过$n-1$个通信链路连接，使得任意两台计算机都可以通过唯一的路由进行通信。若两台计算机之间有通信链路，则称它们相邻。计算机的邻居是与其相邻的一组计算机。

现在需要选择一些计算机作为服务器，服务器可以为其所有邻居都提供服务。若每台客户机(非服务器)都只由一台服务器提供服务，则网络中的一组服务器就形成了完美服务，形成完美服务的最小服务器数叫作完美服务数。现在请你求出这个完美服务数。

【输入格式】

输入包含多组测试数据。

对于每组测试数据，第一行一个正整数$n(n\leq 10^4)$，表示计算机数，计算机编号为$1\sim n$。

接下来$n-1$行，每行两个整数$x,y$，表示计算机$x$和$y$之间有通信链路。

除最后一组输入以外，每组数据以 $0$ 结尾，最后一组数据以 $-1$ 结尾。

【输出格式】

对于每组测试数据，输出一行一个整数，表示完美服务数。

【样例输入】

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

【样例输出】

2
1