#9191. [GESP样题 八级] 小杨的旅游 普及+/提高

小杨准备前往 B 国旅游。

B 国有 座城市，这 座城市依次以 至 编号。城市之间由 条双向道路连接，任意两座城市之间均可达（即任意两座城市之间存在可达的路径）。

小杨可以通过双向道路在城市之间移动，通过一条双向道路需要 单位时间。

B 国城市中有 座城市设有传送门。设有传送门的城市的编号依次为 。小杨可以从任意一座设有传送门的城市花费 单位时间前往另一座设有传送门的城市。

注：如果两座设有传送门的城市之间存在双向道路，那么小杨可以选择通过双向道路移动，也可以选择通过传送门传送。

小杨计划在 B 国旅游 次。第 次旅游（），⼩杨计划从编号为 的城市前往编号为 的城市，小杨希望你能求出所需要的最短时间。

第一行包含三个正整数 ，分别表示 B 国的城市数量，设有传送门的城市数量，以及小杨计划在 B 国旅游的次数。
接下来 行，每行包含两个正整数 ，表示一条双向道路连接的两座城市的编号。
第 行包含 个正整数，表示设有传送门的城市的编号。
接下来 行，每行包含两个正整数 ，表示小杨第 次旅游行程的起点城市编号与终点城市编号。

输出共 行。第 行（）输出一个非负整数，表示小杨计划第 次旅游从编号为 的城市前往编号为 的城市所需要的最短时间。

样例输入 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

对全部的测试数据，，，，。