#1112. JM的地下水路

内存限制:512 MiB 时间限制:750 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: JM233333

题目描述

wzk用大鲍勃消灭了JM的百万大军,tyx和cty被杀得丢盔卸甲,可是首恶JM却逃跑了。为了给他的渡渡鸟们报仇,wzk一路追杀了JM三天三夜,最终JM逃进了克洛斯贝尔的地下水路。

克洛斯贝尔的地下水路是一个包含 个房间的树形结构,这些房间的编号为 ,此外还要算上地下水路的入口,特别地,记入口的编号为 。这可把wzk整懵逼了,众所周知,克洛斯贝尔的地下水路的地形是令人窒息的复杂。而且wzk他只有一个人,如果他追错路的话,JM随时可能趁机逃脱。

幸好wzk有地下水路的全部地图,他知道JM也有地图,而且JM在逃跑时一定会往可达房间个数最多的方向跑,这样wzk就有更大的几率追错路,他就可以趁机逃脱了。至于所谓的可达房间个数,是指从 出发向更深的地方可能到达的房间数。进一步讲,我们可以把地下水路视为一棵以 为根节点的树,那么节点 的可达房间个数即为以 为根节点的子树中的节点个数。

根据wzk的预测,JM从 出发不断逃跑直到无路可走为止。每当JM从某个房间出发逃跑时,将会选择该房间的所有相邻房间中,可达房间个数最多的房间,且JM不走回头路。如果这样的房间个数不止一个,则选择编号最小的房间(因为JM急于逃跑,不能再进行更深入的思考了)。现在你需要帮wzk算出,JM最终逃到了哪个房间,如果算不出来,他就会把你抓去喂qz。

输入格式

第一行一个正整数 表示房间个数,不包括入口。

接下来 行,每行两个正整数 表示一条双向道路。

保证输入的是一棵树。

输出格式

输出一行一个正整数表示答案。

样例

样例输入1

4
1 2
1 3
2 4

样例输出1

4

样例输入2

9
1 2
1 3
2 5
2 4
4 9
4 8
5 7
5 6

样例输出2

8

数据范围与提示