重拳出击

题目描述

小 Z 和 $m$ 个 Youyou 在一棵树上相遇了! 这棵树上,每条边的长度都是 $1$。 初始时,小 Z 在 $x$ 号节点上,并且有一把射程为 $k$ 的枪。 因为小 Z 技术精湛,所以 Youyou 一打就死,而小 Z 永远不会死掉。 小 Z 和 Youyou 都按回合行动,在每一回合中,按照下面的顺序行动: 1. 回合计数器 $+1$(初始为 $0$)。 2. 小 Z 可以用枪射死与小 Z 树上距离小于等于 $k$ 的所有 Youyou。 3. 如果所有 Youyou 都被消灭了,游戏结束,这时回合计数器的值就是小 Z 用的回合数。 4. 小 Z 可以选择沿着一条边,移动到任意相邻节点,也可以选择不动。 5. 所有 Youyou 都会沿着他和小 Z 的简单路径向小 Z 移动一条边的距离。如果此时他们在同一个节点,则不动。 小 Z 需要求出消灭所有敌人需要的最小回合数。

输入输出格式

输入格式


第一行一个正整数 $n$。 接下来 $n-1$ 行每行两个正整数,表示这棵树上的一条边。 接下来一行一个正整数 $m$。 接下来一行 $m$ 个正整数,第 $i$ 个数表示第 $i$ 个 Youyou 的初始所在节点。 最后一行两个整数,$k$ 和小 Z 自己的初始所在节点号 $x$。

输出格式


一行一个正整数,最小回合数。

输入输出样例

输入样例 #1

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

输出样例 #1

3

输入样例 #2

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

输出样例 #2

2

说明

**样例 2 解释** ![](https://cdn.luogu.com.cn/upload/image_hosting/75xvvplh.png) 小 Z 可以在第一回合射死后两个 Youyou,然后从节点 $5$ 移动到节点 $2$。剩余的两个 Youyou 也会移动到节点 $2$。第二回合小 Z 可以消灭所有 Youyou。可以证明这就是最优方案。 **数据规模与约定** * Subtask 1(10 分):$1 \le n,m \le 20$; * Subtask 2(15 分):$1 \le n,m \le 2\times 10^3$; * Subtask 3(30 分):$1 \le n,m \le 4\times 10^4$; * Subtask 4(45 分):$1 \le n,m \le 4\times 10^5$。 对于全部的数据,$1 \le n,m \le 4\times 10^5$,$0 \le k \le 10^6$。