#include<bits/stdc++.h> using namespace std; #define int long long #define pii pair<int,int> #define fr first #define sc second #define mk make_pair #define pb push_back const int MAXN=1000010; int read(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();return x*f;} int n,m,k,t,c,cnt; int id[MAXN],fa[MAXN],siz[MAXN],sz[MAXN],son[MAXN][2],v1[MAXN]; int f[MAXN][2]; pii s[MAXN]; int ty[MAXN],a[MAXN],b[MAXN],as[MAXN]; vector<pii>Q[MAXN]; stack<pii>st; int fid(int x){return x==fa[x]?x:fid(fa[x]);} void mrge(int x,int y){ x=fid(x),y=fid(y); if(sz[x]>sz[y])swap(x,y); if(x!=y)fa[x]=y,siz[y]+=siz[x],sz[y]+=sz[x],st.push(mk(x,y)); } void pop(){ int x=st.top().fr,y=st.top().sc;st.pop(); fa[x]=x,siz[y]-=siz[x],sz[y]-=sz[x]; } void init(){ n=read(),m=read(),k=read(),t=read(),c=read(); for(int i=1;i<=m;i++)s[i].fr=read(),s[i].sc=read(); for(int i=1;i<=k;i++){ a[i]=read(),b[i]=read(); if(a[i]==1)ty[b[i]]=1; if(a[i]==2)siz[b[i]]=1; if(a[i]==3)siz[b[i]]=0; } for(int i=1;i<=t;i++){ int x=read(),y=read(); Q[y].pb(mk(x,i)); } for(int i=1;i<=n;i++)fa[i]=i,sz[i]=1,siz[i]=0; for(int i=1;i<=m;i++)if(!ty[i])mrge(s[i].fr,s[i].sc); for(int i=1;i<=n;i++)if(fa[i]==i)id[i]=++cnt; for(int i=k;i>=1;i--){ if(a[i]==1){ int u=s[b[i]].fr,v=s[b[i]].sc; if(fid(u)!=fid(v)){ cnt++; int x=id[fid(u)],y=id[fid(v)]; mrge(u,v),id[fid(u)]=cnt; son[cnt][0]=x,son[cnt][1]=y; f[cnt][0]=max(f[x][0]+v1[x],f[y][0]+v1[y]); f[cnt][1]=max({f[x][1]+v1[x],f[y][1]+v1[y],f[x][0]+v1[x]+f[y][0]+v1[y]}); } else a[i]=b[i]=0; } if(a[i]==2)v1[id[fid(b[i])]]++; } } int dl[MAXN]; bool ck[MAXN]; void slv(){init(); while(!st.empty())st.pop(); for(int i=1;i<=cnt;i++)v1[i]=0; for(int i=1;i<=n;i++)fa[i]=i,sz[i]=1,siz[i]=0;cnt=0; for(int i=1;i<=k;i++){ if(a[i]==1)ty[b[i]]=1; if(a[i]==2)siz[b[i]]=1; if(a[i]==3)siz[b[i]]=0,dl[b[i]]=i; } for(int i=1;i<=n;i++)if(!dl[i])dl[i]=k+1; for(int i=1;i<=m;i++)if(!ty[i])mrge(s[i].fr,s[i].sc); for(int i=1;i<=n;i++)if(fa[i]==i)id[i]=++cnt; for(int i=k;i>=1;i--){ if(a[i]==1){ int u=s[b[i]].fr,v=s[b[i]].sc; if(fid(u)!=fid(v)){ cnt++; mrge(u,v),id[fid(u)]=cnt; } } if(a[i]==2)v1[id[fid(b[i])]]++,siz[fid(b[i])]--; if(a[i]==3)siz[fid(b[i])]++; for(auto o:Q[i]){ o.fr=fid(o.fr); int rt=id[o.fr],ttmp=v1[rt]; for(int j=i-1;j>=max(1ll,i-c);j--)if(a[j]==2)ck[b[j]]=fid(b[j])==o.fr; for(int j=i-1;j>=max(1ll,i-c);j--){ if(a[j]==1){ int u=s[b[j]].fr,v=s[b[j]].sc; cnt++; mrge(u,v),id[fid(u)]=cnt; } if(a[j]==2)v1[id[fid(b[j])]]++,siz[fid(b[j])]--; if(a[j]==3)siz[fid(b[j])]++; } int now=id[fid(o.fr)],res=siz[fid(o.fr)]+v1[now]; for(int j=max(1ll,i-c);j<i;j++){ if(a[j]==1){ cnt--; pop(); id[fid(s[b[j]].fr)]=son[cnt+1][0],id[fid(s[b[j]].sc)]=son[cnt+1][1]; if(now==cnt+1){ int ct=0; for(int jj=j;jj<i;jj++)if(a[jj]==2){ if(ck[b[jj]]&&dl[b[jj]]>=i)ct++; } int x=son[now][0],y=son[now][1]; if(y==id[fid(o.fr)])swap(x,y); as[o.sc]=max(as[o.sc],res+ct+f[y][0]+v1[y]+f[rt][0]+ttmp); res+=v1[x],now=x; } } if(a[j]==2)v1[id[fid(b[j])]]--,siz[fid(b[j])]++; if(a[j]==3)siz[fid(b[j])]--; } as[o.sc]=max(as[o.sc],res+f[rt][1]); for(int j=i-1;j>=max(1ll,i-c);j--)if(a[j]==2)ck[b[j]]=0; } } for(int i=1;i<=t;i++)printf("%lld\n",as[i]); } signed main(){ // freopen("save.in","r",stdin);freopen("save.out","w",stdout); slv(); // cerr<<clock()*1.0/CLOCKS_PER_SEC<<"s\n"; return 0; }