Minimum Number of Expansion Operations

Given a tree with \(n\) nodes and a designated root \(k\), initially there is exactly one "extensible" node \(z\). We can perform two kinds of expansion operations:

• Type I Expansion: From an extensible node \(u\), mark all nodes in the subtree of \(u\) (with respect to the rooted tree) and also all ancestors of \(u\) that are within distance \(\le p\) (i.e. the first \(p\) ancestors) as extensible. In formula, if \(A(u)\) denotes the set of ancestors of \(u\) (excluding \(u\) itself), then add all nodes in \(subtree(u) \cup \{v \in A(u): d(u,v) \le p\}\).
• Type II Expansion: From an extensible node \(u\), mark all nodes whose depth is equal to the depth of \(u\).

The goal is to make all nodes in the tree become extensible by performing a sequence of expansion operations. Find the minimum number of operations needed.

Note: The depth of a node is defined as its distance from the root \(k\) (with the root having depth \(0\)).

inputFormat

The first line contains four integers \(n\), \(k\), \(p\) and \(z\) denoting the number of nodes, the root of the tree, the parameter for Type I expansion, and the index of the initially extensible node respectively.

Each of the next \(n-1\) lines contains two integers \(u\) and \(v\) representing an undirected edge between nodes \(u\) and \(v\). It is guaranteed that the given graph is a tree.

outputFormat

Output a single integer: the minimum number of expansion operations required to mark all the nodes as extensible.

sample

5 1 1 3
1 2
1 3
2 4
2 5

2