小杨准备前往 B 国旅游。
B 国有 n 座城市,这 n 座城市依次以 1 至 n 编号。城市之间由 n−1 条双向道路连接,任意两座城市之间均可达(即任意两座城市之间存在可达的路径)。
小杨可以通过双向道路在城市之间移动,通过一条双向道路需要 1 单位时间。
B 国城市中有 k 座城市设有传送门。设有传送门的城市的编号依次为 b1,b2,⋯,bk。小杨可以从任意一座设有传送门的城市花费 0 单位时间前往另一座设有传送门的城市。
注:如果两座设有传送门的城市之间存在双向道路,那么小杨可以选择通过双向道路移动,也可以选择通过传送门传送。
小杨计划在 B 国旅游 q 次。第 i 次旅游(1≤i≤q),⼩杨计划从编号为 ui 的城市前往编号为 vi 的城市,小杨希望你能求出所需要的最短时间。
第一行包含三个正整数 n,k,q,分别表示 B 国的城市数量,设有传送门的城市数量,以及小杨计划在 B 国旅游的次数。
接下来 n−1 行,每行包含两个正整数 xi,yi,表示一条双向道路连接的两座城市的编号。
第 n+1 行包含 k 个正整数,表示设有传送门的城市的编号。
接下来 q 行,每行包含两个正整数 ui,vi,表示小杨第 i 次旅游行程的起点城市编号与终点城市编号。
输出共 q 行。第 i 行(1≤i≤q)输出一个非负整数,表示小杨计划第 i 次旅游从编号为 ui 的城市前往编号为 vi 的城市所需要的最短时间。
7 2 1 5 7 3 6 2 3 1 5 5 4 1 2 7 4 3 7
4
5 0 3 2 3 5 1 5 2 1 4 4 5 1 4 4 3
2 1 4
| 子任务 | 分值 | n≤ | k≤ | q≤ |
|---|---|---|---|---|
| 1 | 30 | 500 | 500 | 1 |
| 2 | 30 | 2×105 | 0 | 2×105 |
| 3 | 40 | 2×105 | 2×105 | 2×105 |
对全部的测试数据,1≤n≤2×105,0≤k≤n,1≤xi,yi,ui,vi≤n,ui=vi。