410199: GYM103973 I Photos

ZCY and YYH are good friends. One day, ZCY took a photo of YYH eating a hamburger, and she wants to stick it on every building in the school.

The school contains $$$n$$$ buildings connected with $$$n-1$$$ roads, and there is exactly one path between any two buildings. Initially, ZCY is at building $$$a$$$, and YYH is at building $$$b$$$. In every minute, both of them can walk along a road to the building on the other side. ZCY wants to visit as many buildings as she can, so that she can stick YYH's photos on them. Of course YYH does not want her photo to be found on too many building, so she will try to catch ZCY and stop her as soon as possible. At any moment when YYH and ZCY are at the same building or on the same road, ZCY will be caught by YYH.

Now ZCY wants you to tell her the maximum number of photos that she can stick on the buildings.

The first line contains three integers $$$n\ (1\le n\le 10^6)$$$, $$$a$$$ and $$$b\ (1\le a,b\le n)$$$ as described above.

Each of the following $$$n-1$$$ lines contains two integers $$$u$$$ and $$$v\ (1\le u,v\le n)$$$, indicating a road between $$$u$$$ and $$$v$$$.

Output an integer indicating the maximum number of buildings ZCY can visit.

5 4 3
1 2
1 3
2 4
2 5

3

3 2 2
1 2
2 3

0

In the first example, the buildings that ZCY visit are $$$4\rightarrow 2\rightarrow 5$$$ and YYH are $$$3\rightarrow 1\rightarrow 2$$$. ZCY will be caught by YYH at building $$$5$$$ eventually.