Description

网络由$n$ 台计算机组成，这些计算机通过$n$ -$1$个通信链路连接，使得任意两台计算机都可以通过唯一的路由进行通信。若两台计算机之间有通信链路，则称它们相邻。计算机的邻居是与其相邻的一组计算机。需要选择一些计算机作为服务器，服务器可以为其所有邻居都提供服务。若每台客户机$（$非服务器$）$都只由一台服务器提供服务，则网络中的一组服务器就形成了完美服务，形成完美服务的最小服务器数叫作完美服务数。例如，下图显示了由$6$台计算机组成的网络，其中黑色节点表示服务器，白色节点表示客户机。图$($$a$$)$中的服务器$3$和$5$不形成完美服务，因为客户机$4$与服务器$3$和$5$相邻，由两台服务器提供服务。图$($$b$$)$中的服务器$3$和$4$形成完美服务，且完美服务数等于$2$。

Input

输入包含多个测试用例。每个测试用例的第$1$行都包含一个正整数$n$ $（$$n$ $≤$$1$$0$$0$$0$$0$$）$，表示网络中的计算机数，编号为$1$～$n$ 。接下来的$n$ -$1$行，每行都包含两个正整数，表示一个通信链路。第$n$ +$1$行的$0$表示第$1$个测试用例的结束，-$1$表示整个输入的结束。

Output

对每个测试用例，都单行输出完美服务数。

Samples

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

2
1

来源

POJ3398/UVA1218