Bessie’s Farm Escape

Bessie has gone into hiding on a remote farm consisting of N barns and N-1 bidirectional tunnels forming a tree; that is, there exists a unique path between any pair of barns. A barn is considered an exit if it has a degree of 1 (i.e. it is connected by only one tunnel). When morning comes, Bessie surfaces at barn K and attempts to escape to any exit. However, the law quickly locates her and dispatches farmers from the exit barns. Both Bessie and the farmers move at the same speed – in each time step, a move from a barn to an adjacent barn is allowed.

The farmers catch Bessie if at any time a farmer and Bessie are either in the same barn or crossing the same tunnel simultaneously. Conversely, Bessie escapes if she reaches an exit before any farmer can catch her.

Your task is to determine the minimum number of farmers required to guarantee Bessie’s capture, assuming the farmers are optimally distributed among the exit barns.

One useful approach is as follows. First, compute for every barn v the distance to the nearest exit. In \( \LaTeX \) format, let this be:

[ d_f(v)=\min_{x;:;x \text{ is an exit}} ; dist(v, x). ]

Also, compute the distance from barn K (where Bessie starts) to every barn v, denoted by \( d_b(v) \). The crucial observation is that if Bessie reaches a barn \( v \) with

[ d_b(v) \ge d_f(v), ]

then a farmer coming from that exit can meet her (or intercept her along the tunnel). Consequently, one can perform a DFS starting at barn K and whenever such a vertex is reached, count one farmer needed and do not explore that branch further. The sum of such counts is the answer.

inputFormat

The first line contains two integers \( N \) and \( K \) (with \( 2 \le N \le 10^5 \)), representing the number of barns and the barn at which Bessie surfaces, respectively.

The following \( N-1 \) lines each contain two integers \( u \) and \( v \), indicating that there is a bidirectional tunnel between barns \( u \) and \( v \) (1-indexed).

outputFormat

Output a single integer — the minimum number of farmers that need to be deployed at the exits to guarantee that Bessie is caught.

sample

2 1
1 2

1