小杨准备前往 B 国旅游。
B 国有 n 座城市，这 n 座城市依次以 1 至 n 编号。城市之间由 n−1 条双向道路连接，任意两座城市之间均可达（即任意两座城市之间存在可达的路径）。
小杨可以通过双向道路在城市之间移动，通过一条双向道路需要 1 单位时间。
B 国城市中有 k 座城市设有传送门。设有传送门的城市的编号依次为 b1,b2,⋯,bk。小杨可以从任意一座设有传送门的城市花费 0 单位时间前往另一座设有传送门的城市。
注：如果两座设有传送门的城市之间存在双向道路，那么小杨可以选择通过双向道路移动，也可以选择通过传送门传送。
小杨计划在 B 国旅游 q 次。第 i 次旅游（1≤i≤q），⼩杨计划从编号为 ui 的城市前往编号为 vi 的城市，小杨希望你能求出所需要的最短时间。
7 2 1
5 7
3 6
2 3
1 5
5 4
1 2
7 4
3 7
4
输入 #1复制
7 2 1 5 7 3 6 2 3 1 5 5 4 1 2 7 4 3 7
输出 #1复制
4
输入 #2复制
5 0 3 2 3 5 1 5 2 1 4 4 5 1 4 4 3
输出 #2复制
2 1 4说明/提示
对全部的测试数据，1≤n≤2×105，0≤k≤n，1≤xi,yi,ui,vi≤n，ui=vi。
子任务 分值 n≤ k≤ q≤ 1 30 500 500 1 2 30 2×105 0 2×105 3 40 2×105 2×105 2×105