Chase the Mouse in the Maze

You are given a maze consisting of n rooms and n-1 corridors forming a tree (i.e. a connected acyclic graph). Two special rooms are designated: one contains a trap and one is the starting room where a mouse is placed. Initially, all corridors are clean.

The game proceeds in discrete turns. At the beginning of each turn, the manager (you) may perform at most one operation:

• Block a corridor so that it becomes permanently unavailable (it cannot be unblocked later).
• Clean a corridor (which had become dirty because the mouse used it) so that it is available again.

After your operation (or if you choose to skip), the mouse will move along one corridor that is both clean and unblocked to an adjacent room. While moving, the corridor it traverses becomes dirty. The mouse will move if at least one such corridor exists. Otherwise, it stays put.

The manager's goal is to force the mouse to eventually enter the trap room using as few operations as possible. On the other hand, the mouse will choose its moves to maximize the number of operations you must perform. Both parties play optimally.

Optimal Strategy and Analysis:

Let P be the unique simple path from the mouse’s starting room s to the trap room t. The manager wants to force the mouse to follow this path. However, when the mouse is at a room v on P (except the trap room), if there are any extra corridors (i.e. corridors not lying on P) available, the mouse may choose to deviate, forcing you to later perform an extra cleaning operation to bring it back on track.

An optimal strategy is to preemptively block off these diversionary corridors. However, since you can only operate once per turn, you cannot block all such corridors immediately. In particular, when the mouse is at a room v on P:

• If v = s (the start), then there are deg(s) - 1 extra corridors. You have a chance to block one before the mouse moves. If more than one extra corridor remains unblocked, the mouse will take one and force you to later clean the used corridor. Thus, the cost in operations incurred at s is deg(s) - 1.
• For an interior node v on P (i.e. v not equal to s or t), the extra corridors count is deg(v) - 2 (since two corridors lie on P). Hence, the cost here is deg(v) - 2.

Once the mouse reaches t (the trap room), the game ends immediately (the trap room is absorbing). Therefore, no operations are needed at t.

Thus, if both sides play optimally, the minimum number of operations required by the manager is given by:

$$ Operations = (\deg(s) - 1) + \sum_{v\in P \setminus \{s,t\}} (\deg(v) - 2). $$

Input Format: The maze is given as a tree. The first line contains three integers: n, s, and t — the number of rooms, the starting room of the mouse, and the trap room respectively. Each of the following n-1 lines contains two integers u and v indicating that there is a corridor between room u and room v.

Output Format: Output a single integer representing the minimum number of operations the manager must perform under optimal play.

inputFormat

The first line contains three integers n, s, and t (1 ≤ n ≤ 10⁵), where n is the number of rooms, s is the starting room for the mouse, and t is the trap room. Following that, there are n-1 lines, each containing two integers u and v (1 ≤ u, v ≤ n), representing a corridor between rooms u and v. It is guaranteed that these corridors form a tree (i.e. a connected acyclic graph).

outputFormat

Output a single integer — the minimum number of operations required by the manager if both the manager and the mouse play optimally.

sample

2 1 2
1 2

0

</p>