Description

Xiao Z meets $m$ Youyou on a tree.

On this tree, the length of every edge is $1$.

At the beginning, Xiao Z is at node $x$, and has a gun with range $k$.

Because Xiao Z is very skilled, each Youyou dies instantly when shot, and Xiao Z will never die.

Xiao Z and the Youyou take turns. In each round, they act in the following order:

1. The round counter $+1$ (initially $0$).

2. Xiao Z can use the gun to shoot and kill all Youyou whose distance to Xiao Z on the tree is less than or equal to $k$.

3. If all Youyou have been eliminated, the game ends. The value of the round counter at this time is the number of rounds Xiao Z used.

4. Xiao Z may choose to move along one edge to any adjacent node, or choose to stay.

5. Each Youyou moves one edge along the simple path from itself to Xiao Z. If it is already on the same node as Xiao Z, it does not move.

Xiao Z needs to find the minimum number of rounds required to eliminate all enemies.

Input Format

The first line contains a positive integer $n$.

The next $n-1$ lines each contain two positive integers, representing an edge of the tree.

The next line contains a positive integer $m$.

The next line contains $m$ positive integers. The $i$-th number represents the initial node of the $i$-th Youyou.

The last line contains two integers, $k$ and Xiao Z’s initial node $x$.

Output Format

Output one positive integer in a single line: the minimum number of rounds.

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

3

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

2

Hint

Explanation for Sample 2

In the first round, Xiao Z can shoot and kill the last two Youyou, then move from node $5$ to node $2$. The remaining two Youyou will also move to node $2$. In the second round, Xiao Z can eliminate all Youyou. It can be proven that this is the optimal strategy.

Constraints

• Subtask 1 (10 points): $1 \le n,m \le 20$.
• Subtask 2 (15 points): $1 \le n,m \le 2\times 10^3$.
• Subtask 3 (30 points): $1 \le n,m \le 4\times 10^4$.
• Subtask 4 (45 points): $1 \le n,m \le 4\times 10^5$.

For all testdata, $1 \le n,m \le 4\times 10^5$, $0 \le k \le 10^6$.

Translated by ChatGPT 5