ガソリンスタンドが \(K \leq min(N-1,20)\) と少ないので，そこから考える． ガソリンスタンドを経由するせいで，逆に簡単． ガソリンスタンド \(x\) を一つ固定してこれを経由する \(s \rightarrow t\) の最短距離は， \(dis[x][s] + dis[x][t]\). よって，BFSで \(dis\) を前計算すればよい．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n,m,q,k; cin >> n >> m >> q >> k;
vll a(k);
rep(i,k){
cin >> a[i];
a[i]--;
}
vvll to(n);
rep(i,m){
ll a, b; cin >> a >> b;
--a, --b;
to[a].push_back(b);
to[b].push_back(a);
}
auto bfs = [&](ll src) -> vll {
vll dis(n, INFL);
queue<ll> que;
auto push = [&](ll v, ll d) -> void {
if(vis[v]) return;
vis[v] = true;
que.push(v);
dis[v] = d;
};
push(src, 0);
while(que.size()){
ll cu = que.front(); que.pop();
ll d = dis[cu];
for(auto ne: to[cu]){
push(ne, d + 1);
}
}
return dis;
};
vvll dis(k);
rep(i,k) dis[i] = bfs(a[i]);
rep(qi,q){
ll s,t; cin >> s >> t;
--s, --t;
ll ans = INFL;
rep(i,k){
chmin(ans, dis[i][s] + dis[i][t]);
}
cout << ans << endl;
}
return 0;
}
