题目描述

乐乐现在工作很忙,他接到了一个任务,要把一个1GiB的文件复制到$n$台电脑里面去.

而且电脑网络组成了一棵树.

一开始这颗树上只有两台电脑有这个文件,在一个时间内,每台电脑能够把文件复制到与它相邻的任意一台电脑中(只能一台）.

问至少需要多长时间才能使所有的电脑中都有这个文件.

输入格式

三个整数 $n,x,y$,表示有 $n$台电脑,一开始在$x,y$ 里面有文件($x!=y$) .

接下来 $n-1$行,每行两个整数 $x,y$,表示 $x,y$之间有一条边.

输出格式

一个整数,表示最少需要多少时间

样例

6 2 1
1 2
2 3
2 4
1 5
5 6

2

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

4

17 1 2
1 3
1 4
4 6
6 7
3 8
3 9
3 10
1 13
13 5
13 11
13 12
13 14
14 15
15 16
15 17
14 2

5

数据范围

• 子任务1(10分)︰树是一条链，$n ≤100$，且$i$和$i＋1$连边子
• 任务2(10分) :树是一条链,$n ≤300000$，且$i$和$i＋1$连边
• 子任务3(10分) :树是一条链，$n≤300000$
• 子任务4(15分) :$n ≤1000$,且$x$和$y$相邻
• 子任务5(15分) :$n ≤1000$
• 子任务6(20分) :$n ≤300000$ ,且$x$和$y$相邻
• 子任务7(20分) :$n≤300000$