릭의 가운

릭은 가운을 세탁하려고 한다. 그런데 다음 미친 모험까지 시간이 별로 없어서, 제대로 빨래하는 대신 가운의 $s$개 점을 특수 용액으로 적셨다. 지금은 가운이 마르기를 기다리는 중이다.

릭이 만든 용액은 일종의 의지가 있어서, 증발하지 않고 가운 위로 퍼져 나간다. 가운은 $n$개의 정점과 $m$개의 간선을 가진 무방향 그래프로 나타낼 수 있다. 용액으로 적신 점은 서로 다른 $k$개의 정점이다. 가운에는 오래되어서 $t$개의 구멍도 있는데(서로 다른 $t$개의 정점), 용액은 이 구멍을 통해서 빠져나간다.

릭은 비효율적으로 움직이는 용액을 만들지 않았다. 각 초기 점의 용액은 가장 가까운 구멍까지 흘러가서 그 구멍으로 모두 빠져나간다. 천의 간선 하나를 지나는 데 1단위 시간이 걸린다. 같은 간선으로 얼마든지 많은 양의 용액이 동시에 흐를 수 있다.

릭은 모든 용액이 구멍으로 빠져나가는 데 걸리는 시간을 계산했고, 너무 오래 걸린다고 판단했다. 그래서 과정을 빠르게 하려고 가운의 아무 정점에나 구멍을 하나 더 뚫으려 한다. 모든 방울이 가장 가까운 구멍에 도달하는 데 걸리는 시간을 최소로 만드는 정점을 찾아라.

용액은 즉시 작용하므로, 용액이 있는 자리에 구멍을 뚫을 수 있다. 그렇게 하는 것이 답을 최소로 만든다면 그렇게 해도 된다. 선택지가 여러 개라면, 구멍을 추가했을 때 필요한 거리가 최소가 되는 정점 중 번호가 가장 작은 것을 찾아라.

첫 줄에 공백으로 구분된 정수 $n$, $m$, $s$, $t$가 주어진다. 각각 가운의 정점 수, 간선 수, 처음 적셔진 점의 수, 구멍의 수이다. ($1 \leqslant n, m \leqslant 2 \cdot 10^5$; $1 \leqslant s \leqslant \min(n, 100)$; $1 \leqslant t \leqslant n$)

다음 줄에는 릭이 용액으로 적신 정점의 번호인, 서로 다른 $k$개의 정수 $p_i$가 공백으로 구분되어 주어진다 ($1 \leqslant p_i \leqslant n$).

다음 줄에는 가운에 구멍이 있는 정점의 번호인, 서로 다른 $t$개의 정수 $q_i$가 공백으로 구분되어 주어진다 ($1 \leqslant q_i \leqslant n$).

이어지는 $m$개의 줄에는 각각 두 정수 $v_i$와 $u_i$가 공백으로 주어지며, 정점 $u_i$와 $v_i$ 사이에 간선이 있음을 뜻한다 ($1 \leqslant v_i, u_i \leqslant n$).

한 줄에 구멍을 뚫을 정점의 번호와 가운이 마르는 데 걸리는 최소 시간을 공백으로 구분하여 출력한다.

다른 어떤 선택으로도 답이 개선되지 않는다면, 이미 구멍이 있는 정점의 번호를 출력해도 된다. 답이 여러 개라면 정점 번호가 가장 작은 것을 출력한다(그 정점에 이미 구멍이 있는지는 상관없다).