#include using namespace std; int main(void) { int n,k,m,p; cin >> n >> k >> m >> p; vector u(m); vector v(m); vector> g(n); for(int i=0;i> u[i] >> v[i]; --u[i]; --v[i]; g[u[i]].emplace_back(v[i]); g[v[i]].emplace_back(u[i]); } vector s(n); for(int i=0;i> s[i]; } vector x(k); vector day(n,INT_MAX-1); int ans=0; priority_queue,vector>,greater>> q; for(int i=0;i> x[i]; --x[i]; day[x[i]]=0; q.emplace(p,0,x[i]); q.emplace(s[x[i]],1,x[i]); } while(!q.empty()){ auto [d,t,h]=q.top(); q.pop(); if(t){ for(auto next: g[h]){ if(day[next]