U370913 王子的地盘

有一个国王要把他的领土分给他的两个王子，领土是N座城市由N-1条长度相同的路连接成一棵树的形状。每位王子先要选择一个城市作为他的王府，国王规定其他的城市离谁的王府近就归谁所有，如果一样远的话就归大王子所有。现在假设两位王子的智囊团都采取最优策略来选，且大王子先选，问大王子最多能够得到多少城市？

第一行一个整数N，表示城市总数 接下来N-1行，每行两个整数x,y用空格隔开，表示x城和y城之间有一条路连通。

输出一行，表示大儿子最多可以得到的城市总数。

30%的数据，1