UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#2466. [中山市选2009]树

统计 下载数据

Description

 图论中的树为一个无环的无向图。给定一棵树,每个节点有一盏指示灯和一个按钮。如果节点的按扭被按了,那么该节点的灯会从熄灭变为点亮(当按之前是熄灭的),或者从点亮到熄灭(当按之前是点亮的)。并且该节点的直接邻居也发生同样的变化。
 开始的时候,所有的指示灯都是熄灭的。请编程计算最少要按多少次按钮,才能让所有节点的指示灯变为点亮状态。

Input

 输入文件有多组数据。
 输入第一行包含一个整数n,表示树的节点数目。每个节点的编号从1到n。
 输入接下来的n – 1行,每一行包含两个整数x,y,表示节点x和y之间有一条无向边。
 当输入n为0时,表示输入结束。

Output

对于每组数据,输出最少要按多少次按钮,才能让所有节点的指示灯变为点亮状态。每一组数据独占一行。

Sample Input

3
1 2
1 3
0

Sample Output

1

Hint

对于100%的数据,满足1 <= n <=100

Source