//By SiriusRen#include <bits/stdc++.h>using namespace std;const int N=400500;int n,m,k,type,ch[N][2],fa[N],minn[N],rev[N],q[N],top,pre[N];int root[N],tree[N*50],lson[N*50],rson[N*50],cnt,xx,yy,ans;struct Road{int x,y,wei;}road[N];bool isroot(int p){return ch[fa[p]][0]!=p&&ch[fa[p]][1]!=p;}void push_up(int p){    minn[p]=p;    if(road[minn[ch[p][0]]].wei<road[minn[p]].wei)minn[p]=minn[ch[p][0]];    if(road[minn[ch[p][1]]].wei<road[minn[p]].wei)minn[p]=minn[ch[p][1]];}void push_down(int p){rev[ch[p][0]]^=1,rev[ch[p][1]]^=1,rev[p]=0,swap(ch[p][0],ch[p][1]);}void rotate(int p){    int q=fa[p],y=fa[q],x=(ch[q][1]==p);    ch[q][x]=ch[p][!x],fa[ch[q][x]]=q;    ch[p][!x]=q,fa[p]=y;    if(!isroot(q)){        if(ch[y][1]==q)ch[y][1]=p;        if(ch[y][0]==q)ch[y][0]=p;    }fa[q]=p;push_up(q);}void splay(int x){    q[++top]=x;    for(int i=x;!isroot(i);i=fa[i])q[++top]=fa[i];    while(top){if(rev[q[top]])push_down(q[top]);top--;}    for(int y=fa[x];!isroot(x);rotate(x),y=fa[x])if(!isroot(y)){        if((ch[y][0]==x)^(ch[fa[y]][0]==y))rotate(x);        else rotate(y);    }push_up(x);}void access(int x){for(int t=0;x;t=x,x=fa[x])splay(x),ch[x][1]=t,push_up(x);}void makeroot(int x){access(x),splay(x),rev[x]^=1;}bool connected(int x,int y){while(fa[x])x=fa[x];while(fa[y])y=fa[y];return x==y;}void link(int x,int y){makeroot(x),fa[x]=y;}void split(int x,int y){makeroot(x),access(y),splay(y);}void cut(int x,int y){split(x,y),ch[y][0]=fa[x]=0;push_up(y);}void insert(int l,int r,int &pos,int last,int wei){    pos=++cnt,tree[pos]=tree[last]+1;    if(l==r)return;    int mid=(l+r)>>1;    if(mid<wei)lson[pos]=lson[last],insert(mid+1,r,rson[pos],rson[last],wei);    else rson[pos]=rson[last],insert(l,mid,lson[pos],lson[last],wei);}int query(int l,int r,int pos,int last,int L,int R){    if(l>=L&&r<=R)return tree[pos]-tree[last];    int mid=(l+r)>>1;    if(mid<L)return query(mid+1,r,rson[pos],rson[last],L,R);    else if(mid>=R)return query(l,mid,lson[pos],lson[last],L,R);    else return query(l,mid,lson[pos],lson[last],L,R)+query(mid+1,r,rson[pos],rson[last],L,R);}int main(){    scanf("%d%d%d%d",&n,&m,&k,&type);    for(int i=0;i<=n;i++)road[i].wei=0x3f3f3f3f;    for(int i=n+1;i<=n+m;i++)scanf("%d%d",&road[i].x,&road[i].y),road[i].wei=i;    for(int i=n+1;i<=n+m;i++){        if(connected(road[i].x,road[i].y)){            if(road[i].x==road[i].y){pre[i-n]=i-n;continue;}            split(road[i].x,road[i].y);            int t=minn[road[i].y];            pre[i-n]=road[t].wei-n;            cut(road[t].x,t),cut(road[t].y,t);        }        link(road[i].x,i),link(road[i].y,i);    }    for(int i=1;i<=m;i++)insert(0,m,root[i],root[i-1],pre[i]);    while(k--){        scanf("%d%d",&xx,&yy);        if(type)xx^=ans,yy^=ans;        printf("%d\n",ans=n-query(0,m,root[yy],root[xx-1],0,xx-1));    }}