题目描述

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

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

输入格式

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

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

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

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

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

2
0

样例2见下载文件

对于 30% 的数据， $n,m,k,q\leq 10$

对于 50% 的数据， $n,m,k,q\leq 1000$

对于另外 20% 的数据， $k\leq 10$ ；

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

对于所有数据， $1\leq n,m,q\leq 10^5,2\leq k\leq n,1\leq h_i,u_i,v_i,s_i\leq n,0\leq b_i\leq k$ 。保证图连通。