Bob喜欢玩电脑游戏，特别是战略游戏。但是他经常无法找到快速玩过游戏的办法。现在他有个问题。

他要建立一个古城堡，城堡中的路形成一棵无根树。他要在这棵树的节点上放置最少数目的士兵，使得这些士兵能瞭望到所有的路。

注意：某个士兵在一个节点上时，与该节点相连的所有边将都可以被瞭望到。

第一行1个整数 n，表示树中节点的数目；

之后 n-1 行，每行两个数 u,v，表示节点 u,v 之间有一条无向边；

节点标号在 1 到n  之间，保证在输入数据中每条边只出现一次。

输出仅包含一个整数，为所求的最少的士兵数目。

30%数据，n<=20

100%数据，n<=100000