I am looking for help identifying a problem from my country's national olympiad (they steal problems from other countries olympiads and reword them), or some insight as to the solution for this problem. I've tried for a full day, but I haven't managed in (a) finding the source of the problem, or (b) solving the problem. They don't give post an editorial or anything, they just have an online grader.

This is the problem:

Catching Crewmates

Input file: standard input

Output file: standard output

Time limit: 5 seconds

Memory limit: 512 megabytes


The Skeld is a spacecraft which can be modeled as a collection of n rooms numbered 1, 2, . . . , n and n − 1
doors connecting these rooms such there is a unique path between any two rooms.

Currently, there is a single crewmate and a single impostor on the Skeld. The crewmate is initially in the
room x and the impostor is hiding in a vent in the room y.

The crewmate is scared of the impostor and is thus constantly running through the doors between different
rooms, in an attempt to get away from the impostor. The crewmate will also mark any door with a
breadcrumb trail when they run through it, and then know not to pass through that door again. However,
if the floor gets cleaned near a marked door, then the breadcrumb trail will be lost and the crewmate will
be able to run through the door again.

Additionally, right before the crewmate runs through a door, the impostor is able to clean the floor near
any door that has been marked by a breadcrumb trail, close any door permanently, or do nothing.
The impostor wants to catch the crewmate as quickly as possible and would like to know how many
“moves” this would take.

Another way to describe this problem is as a two-player game, where the impostor moves first.
On their turn, the impostor can do any of the following:

• Clean the floor near a door marked with a breadcrumb trail, making it possible for the crewmate
to pass through this door again.

• Close any open door on the Skeld, permanently.

• Do nothing. (This does not count as a move for the impostor)

Note that in no case will the impostor open a door that they have closed before.

On the crewmate’s turn, they will do the following:

• Choose an open and unmarked door to an adjacent room, and run through it, marking the door
with a breadcrumb trail in the process.

• Do nothing only if no such doors exist.

The moment that the crewmate is forced to enter the room where the impostor is hiding, the games ends
and the impostor catches the crewmate.

In this two-player game, the goal of the crewmate is to survive and maximize the number of moves it
takes the impostor to catch them, and the goal of the impostor is to minimize the number of moves it
takes to catch the crewmate.

Assuming both the crewmate and the impostor act optimally, what is the minimum number of moves
(doors closed or cleaned) it will takes the impostor to catch the crewmate?

Input

The first line of input contains three integers n, y, x (1 ≤ y, x ≤ n ≤ 10^6)  from the problem statement.
The next n − 1 lines of input each contain two integers a and b (1 ≤ a, b ≤ n)  indicating a door
connecting two distinct rooms a and b.

Output

Output a single integer  the minimum number of moves it will take the impostor to catch the crewmate,
assuming both act optimally.

Scoring

Subtask 1: (0 Points) Examples.

Subtask 2: (20 Points) n ≤ 10.

Subtask 3: (25 Points) It is guaranteed that there is a door between rooms x and y.

Subtask 4: (20 Points) n ≤ 1000.

Subtask 5: (35 Points) No further constraints.

Example

Input:

10 1 4

1 2

2 3

2 4

3 9

3 5

4 7

4 6

6 8

7 10


Answer:

4

Note

One possible scenario which explains the example output:

• Impostor closes the door between rooms 4 and 7.

• Crewmate runs to room 6. The door between rooms 4 and 6 is now marked.

• Impostor closes the door between rooms 6 and 8.

• Crewmate cannot move.

• Impostor cleans the floor near the door between rooms 4 and 6.

• Crewmate runs to room 4. The door between rooms 4 and 6 is now marked.

• Impostor closes the door between rooms 2 and 3.

• Crewmate runs to room 2. The door between rooms 2 and 4 is now marked.

• Impostor does nothing.

• Crewmate can only run into room 1 and gets caught by the impostor.

I would appreciate it if anybody could give an insight to the solution or a link to the original. thank you.