#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.insert({{p,-1},x}); ms.insert({{s[x],1},x}); c[x] = 1; } while(ms.size()){ auto x = *ms.begin(); ms.erase(ms.find(x)); if(x.first.second==-1){ cure[x.second] = true; }else{ if(!iru[x.second]) continue; for(int u:G[x.second]){ if(!cure[u]){ if(!c[u]){ c[u] = 1; ms.insert({{x.first.first + p,-1},u}); ms.insert({{x.first.first + s[u],1},u}); }else{ iru[u] = false; } } } } } int ans = 0; for(i=0;i