Mirko works at a data centre and today's task is to copy a file sized GiB to computers. The computers are denoted with integers from to and are connected so that they form a so-called tree. More precisely, pairs of computers are directly connected via network cable in a way that there is a unique path between each pair of computers.
Initially, Mirko manually placed the file on two different computers – computer and computer and is now writing commands that will copy the file to all other computers. The file can be copied from computer to computer 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 to computer , it is possible in the next minute to copy the file from computer to computer and from computer to computer .
Determine the minimal amount of time it takes for the file to be copied to all computers.
Input Specification
The first line of input contains the integer and two different integers and – the number of computers and the labels of the computers already containing the file. Each of the following lines contains two different integers and – the labels of the computers directly connected via network cable. The computer network forms a tree, as described in the task.
Output Specification
You must output the required minimal amount of time in minutes.
Constraints
Subtask | Score | Constraints |
---|---|---|
Sample Input 1
6 2 1
1 2
2 3
2 4
1 5
5 6
Sample Output 1
2
Sample Input 2
10 1 2
1 2
2 5
1 3
1 4
4 6
6 7
3 8
3 9
3 10
Sample Output 2
4
Explanation for Sample Output 2
Sample Input 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
Sample Output 3
5
Comments