题目描述

图论中的树为一个无环的无向图。给定一棵树，每个节点有一盏指示灯和一个按钮。如果节点的按扭被按了，那么该节点的灯会从熄灭变为点亮（当按之前是熄灭的），或者从点亮到熄灭（当按之前是点亮的）。并且该节点的直接邻居也发生同样的变化。

开始的时候，所有的指示灯都是熄灭的。请编程计算最少要按多少次按钮，才能让所有节点的指示灯变为点亮状态。

输入格式

输入文件有多组数据。

输入第一行包含一个整数 $n$，表示树的节点数目。每个节点的编号从 $1$ 到 $n$。

输入接下来的 $n–1$ 行，每一行包含两个整数 $x,y$，表示节点 $x$ 和 $y$ 之间有一条无向边。

当输入 $n$ 为 $0$ 时，表示输入结束。

输出格式

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

3
1 2
1 3
0

1

提示

对于 $100\%$ 的数据，满足 $1\le n\le 100$。