Codah Club연습하고, 제출하고, 성장하세요.
로그인
한국어
#000607

TIgra

Liitle Z and Mister S play the game TIgra. TIgra is played on a board consisted of N fields. From a given field, a player can move to another field only if those two fields are connected. Additionally, the board is such that between any two fields there exists exactly one way, i.e. exactly one path, to get from one to another field, for every two fields. By a path we understand a chain of fields such that every two consecutive fields in the chain are connected..


Little Z and Mister S are placed on different fields initially. The goal of Mister Z is to catch Mister S as soon as possible, therefore the goal of Mister S is to remain being uncaught as long as possible. We say that Little Z catches Mister S if they are placed on the same field. They play a sequence of moves, where a single move is defined by the following sequence of events, which appear one after another:
- Mister S chooses a field which is connected to the field he is currently positioned at, and he moves to that field or he stays at the same he is currently at.
- Little Z chooses a field connected to the field he is currently positioned at, and he moves to that field or stays at the same field he is currently at.
- If Little Z and Mister S are not on the same field, then the next move is played, otherwise the game is over.


Assuming that both Little Z and Mister S plays optimally, you should print for how many moves the game is going to last.


InputThe first line of the standard input contains three integers: N, G and T (1 <= G,T <= N <= 100.000) which represent the number of fields on the board, the field at which is Mister S positioned initially, and the field at which is Little Z positioned initially, respectively. In the next N-1 lines are given two integers Ai and Bi what represents that the fields Ai and Bi are connected.

OutputIn the first and the only line of the standard output you should pint for how many moves the game is going to last.


Input:
7 4 1
1 2
1 3
4 1
4 5
6 4
6 7

Output:
3

Explanation:
If Mister S moves to the field 1 in the first move, the game is going to finish after the first move; if he moves to the field 5 then Little Z moves to the field 4 and the game finishes in 2 moves. There is a strategy that Mister S will survive for 3 moves which is:
1. move: Mister S moves to the field 6, Little Z moves to the field 4.
2. move: Mister S moves to the field 7, Little Z moves to the field 6.
3. move: Mister S stays on the field 7, Little Z moves to the fields 7.(If Mister S goes back to the field 6, Little Z will stay on the field 6 and again the game will finish in 3 moves.)

Submit solution

Coming later

The grading service will be connected in a later migration step. You can inspect the task and your previous results now.