//By SiriusRen

#include <bits/stdc++.h>

using namespace std;

const int N=;

int n,m,k,type,ch[N][],fa[N],minn[N],rev[N],q[N],top,pre[N];

int root[N],tree[N*],lson[N*],rson[N*],cnt,xx,yy,ans;

struct Road{int x,y,wei;}road[N];

bool isroot(int p){return ch[fa[p]][]!=p&&ch[fa[p]][]!=p;}

void push_up(int p){

    minn[p]=p;

    if(road[minn[ch[p][]]].wei<road[minn[p]].wei)minn[p]=minn[ch[p][]];

    if(road[minn[ch[p][]]].wei<road[minn[p]].wei)minn[p]=minn[ch[p][]];

}

void push_down(int p){rev[ch[p][]]^=,rev[ch[p][]]^=,rev[p]=,swap(ch[p][],ch[p][]);}

void rotate(int p){

    int q=fa[p],y=fa[q],x=(ch[q][]==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][]==q)ch[y][]=p;

        if(ch[y][]==q)ch[y][]=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][]==x)^(ch[fa[y]][]==y))rotate(x);

        else rotate(y);

    }push_up(x);

}

void access(int x){for(int t=;x;t=x,x=fa[x])splay(x),ch[x][]=t,push_up(x);}

void makeroot(int x){access(x),splay(x),rev[x]^=;}

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][]=fa[x]=;push_up(y);}

void insert(int l,int r,int &pos,int last,int wei){

    pos=++cnt,tree[pos]=tree[last]+;

    if(l==r)return;

    int mid=(l+r)>>;

    if(mid<wei)lson[pos]=lson[last],insert(mid+,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)>>;

    if(mid<L)return query(mid+,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+,r,rson[pos],rson[last],L,R);

}

int main(){

    scanf("%d%d%d%d",&n,&m,&k,&type);

    for(int i=;i<=n;i++)road[i].wei=0x3f3f3f3f;

    for(int i=n+;i<=n+m;i++)scanf("%d%d",&road[i].x,&road[i].y),road[i].wei=i;

    for(int i=n+;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=;i<=m;i++)insert(,m,root[i],root[i-],pre[i]);

    while(k--){

        scanf("%d%d",&xx,&yy);

        if(type)xx^=ans,yy^=ans;

        printf("%d\n",ans=n-query(,m,root[yy],root[xx-],,xx-));

    }

}