#include #include #include #include using namespace std; typedef pair pii; vector G[100010]; int s[100010],c[100010]; bool cure[100010],iru[100010]; int main(){ int i,n,k,m,p; cin >> n >> k >> m >> p; for(i=0;i> u >> v; u--; v--; G[u].push_back(v); G[v].push_back(u); } for(i=0;i>> ms; for(i=0;i> s[i]; for(i=0;i> x; x--; ms[p].push_back({-1,x}); ms[s[x]].push_back({1,x}); c[x] = 1; } while(ms.size()){ auto x = *ms.begin(); ms.erase(x.first); vector> v = x.second; sort(v.begin(),v.end()); vector del; for(auto pp:v){ if(pp.first==-1){ cure[pp.second] = true; }else{ if(!iru[pp.second]) continue; for(int u:G[pp.second]){ if(!cure[u]){ if(!c[u]){ c[u] = 1; ms[x.first + p].push_back({-1,u}); ms[x.first + s[u]].push_back({1,u}); }else{ del.push_back(u); } } } } } for(int u:del){ iru[u] = false; } } int ans = 0; for(i=0;i