19354번 - Education Nightmare 다국어

You are having a nightmare! In the dream, you have finished your education and you are now to start teaching others. And today is your first day! You enter the school building (being a little late) and... of course, you have forgotten which room your class takes place in.

The building consists of $n$ rooms, numbered $1, 2, \ldots, n$. Some pairs of rooms are connected with a passage. You may move between connected rooms, each transfer taking exactly one second. There are exactly $n - 1$ passages in the building, and every room can be reached, given enough time. In other words, the rooms and passages form a tree.

You start in room $s$. If you enter the correct room, you will immediately recognize it and end your quest. Even so, searching all the rooms could take really long... Fortunately, there is one more trick you can use: in the room $m$ there is a complete timetable of all classes. If you ever enter room $m$, you immediately learn where the class is, and you may go there at once, using the shortest route (be advised, though: the room $m$ does not provide any printing, faxing, scanning or photocopy services. You shouldn't ask them about it).

Find the minimal time $t$ needed to find your class in the worst case, that is, the minimal number $t$ for which there is a strategy guaranteeing finding the correct room in $t$ seconds.

The first line of input contains the number of test cases $z$ ($1 \leq z \leq 10^9$). The descriptions of the test cases follow.

The first line of each test case contains three integers: the number of rooms $n$, the starting room $s$, and the room with the timetable $m$ ($1 \leq n \leq 200\,000$, $1 \leq s, m \leq n$). Then, $n - 1$ lines follow, each containing two integers $a, b$ ($1 \leq a, b \leq n$, $a \neq b$), denoting a passage between rooms $a$ and $b$. It is guaranteed that every room can be reached from every other one.

It is possible for the class to take part in room $s$ or in room $m$. It is also possible to start in room $m$.

The total number of rooms in all test cases does not exceed $10^7$.

For each test case, output a single integer: the total number of seconds needed to reach the classroom, assuming the best possible strategy.