土豆城是由 n 个路口和 m 条双向道路构成的，每条双向道路连接两个路口，任意两个路口可以相互到达。此外，城市里设有 k 个酒店，每个酒店位于一个路口。两个路口之间的距离定义为从一个路口到达另一个路口需要经过的最少道路数量。

小土豆计划在土豆城旅游 q 天，第 i 天小土豆打算在第si个路口结束当天的行程，因此想在距离第si个路口最近的地方选择一个酒店。然而，有一些酒店已经被预定满了，第 i 天小土豆无法预定第bi个酒店。

第一行四个整数 n,m,k,q；

接下来一行 k 个整数hi，代表每个酒店所在路口；

接下来 m 行，每行两个整数ui, vi，代表一条双向道路；

接下来 q 行，每行两个整数si, bi，其中如果bi=0则小土豆可以预定任意一个酒店，否则小土豆在第 i 天不能预定第bi个酒店。

输出 q 行，每行一个整数，代表小土豆当天预定的酒店与行程结束位置之间的最短距离。

样例说明：

第一天可以选择 2 号酒店，第二天可以选择 1 号酒店。

数据范围：

对于30%的数据，n,m,k,q<=10；

对于50%的数据，n,m,k,q<=1000；

对于另外20%的数据，k<=10；

对于另外20%的数据，bi=0；

对于所有数据，1<=n,m,q<=10^5,2<=k<=n,1<=hi,ui,vi,si<=n,0<=bi<=k。保证图连通。

SX2023-C