시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB94312433.803%

문제

Mirko works at a data centre and today’s task is to copy a file sized 1 GiB to n computers. The computers are denoted with integers from 1 to n and are connected so that they form a so-called tree. More precisely, n − 1 pairs of computers are directly connected via network cable in a way that there is a unique path between each pair of computers.

Figure 4: In the first sample test, it takes two minutes for the file to be copied to all computers.

Initially, Mirko manually placed the file on two different computers – computer a and computer b and is now writing commands that will copy the file to all other computers. The file can be copied from computer x to computer y only if the two computers are directly connected, and the copying process takes exactly one minute. At any moment, each individual computer can take part in at most one copying process, but it is allowed to have the file being copied between arbitrarily many different pairs of computers at the same time. Therefore, when the copying process ends from computer x to computer y, it is possible in the next minute to copy the file from computer x to computer w and from computer y to computer z.

Determine the minimal amount of time it takes for the file to be copied to all computers.

입력

The first line of input contains the integer n and two different integers a and b (1 ≤ a, bn) – the number of computers and the labels of the computers already containing the file. Each of the following n − 1 lines contains two different integers x and y (1 ≤ x, yn) – the labels of the computers directly connected via network cable. The computer network forms a tree, as described in the task.

출력

You must output the required minimal amount of time in minutes.

서브태스크

번호배점제한
131

2 ≤ n ≤ 1 000

269

1 000 ≤ n ≤ 300 000

예제 입력 1

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

예제 출력 1

2

예제 입력 2

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

예제 출력 2

4

예제 입력 3

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

예제 출력 3

5

힌트

Figure 5: Illustrations of the second and third sample test

채점 및 기타 정보

  • 예제는 채점하지 않는다.