#include<iostream>

#include<cstdio>

#include<cstring>

#define N 400002

using namespace std;

int f[N],a[N],n,m,type,k;

inline int rd(){

    int x=;char c=getchar();bool f=;

    while(!isdigit(c)){if(c=='-')f=;c=getchar();}

    while(isdigit(c)){x=(x<<)+(x<<)+(c^);c=getchar();}

    return f?-x:x;

}

inline int find(int x){return f[x]=f[x]==x?x:find(f[x]);}

struct LCT{

    int ch[N][],fa[N],l[N],tr[N];bool rev[N];

    #define ls ch[x][0]

    #define rs ch[x][1]

    inline bool ge(int x){return ch[fa[x]][]==x;}

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

    inline void pushup(int x){

        tr[x]=x;

        if(ls&&a[tr[ls]]<a[tr[x]])tr[x]=tr[ls];if(rs&&a[tr[rs]]<a[tr[x]])tr[x]=tr[rs];

    }

    inline void rotate(int x){

        int y=fa[x],o=ge(x);

        ch[y][o]=ch[x][o^];fa[ch[y][o]]=y;

        if(!isroot(y))ch[fa[y]][ge(y)]=x;fa[x]=fa[y];

        fa[y]=x;ch[x][o^]=y;pushup(y);pushup(x);

    }

    inline void pushdown(int x){if(rev[x]){rev[x]^=;rev[ls]^=;rev[rs]^=;swap(ls,rs);}}

    inline void _pushdown(int x){if(!isroot(x))_pushdown(fa[x]);pushdown(x);}

    inline void splay(int x){

        _pushdown(x);

        while(!isroot(x)){

            int y=fa[x];

            if(isroot(y))rotate(x);

            else rotate(ge(x)==ge(y)?y:x),rotate(x);

        }

    }

    inline int findroot(int x){

        access(x);splay(x);pushdown(x);

        while(ls)x=ls,pushdown(x);return x;

    }

    inline void access(int x){for(int y=;x;y=x,x=fa[x])splay(x),ch[x][]=y,pushup(x);}

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

    inline void split(int x,int y){makeroot(x);access(y);splay(y);}

    inline void link(int x,int y){makeroot(x);fa[x]=y;}

    inline void cut(int x,int y){split(x,y);fa[x]=ch[y][]=;pushup(y);}

    void dfs(int x){

        if(ls)dfs(ls);cout<<x<<" ";if(rs)dfs(rs);

    }

    #undef ls

    #undef rs

}lct;

int tot,ls[N*],rs[N*],sum[N*],T[N],ans;

void upd(int &cnt,int pre,int l,int r,int x,int y){

    cnt=++tot;ls[cnt]=ls[pre];rs[cnt]=rs[pre];sum[cnt]=sum[pre]+y;

    if(l==r)return;

    int mid=(l+r)>>;

    if(mid>=x)upd(ls[cnt],ls[pre],l,mid,x,y);

    else upd(rs[cnt],rs[pre],mid+,r,x,y);

}

int query(int cnt,int l,int r,int L,int R){

    if(l>=L&&r<=R)return sum[cnt];

    int mid=(l+r)>>,ans=;

    if(mid>=L)ans+=query(ls[cnt],l,mid,L,R);

    if(mid<R)ans+=query(rs[cnt],mid+,r,L,R);

    return ans;

}

struct edge{int x,y;}b[N];

int main(){

    n=rd();m=rd();k=rd();type=rd();

    for(int i=;i<=n;++i)f[i]=i;int x,y;

    for(int i=;i<=n;++i)a[i]=2e9;

    for(int i=;i<=m;++i){

        a[i+n]=i;

        x=rd();y=rd();T[i]=T[i-];b[i].x=x;b[i].y=y;

        if(x==y)continue;

        if(find(x)==find(y)){

            lct.split(x,y);

            int id=lct.tr[y];

        //    lct.dfs(y);cout<<" ??? "<<x<<" "<<y<<" "<<id<<" "<<lct.findroot(y)<<endl;

            lct.cut(id,b[id-n].x);lct.cut(id,b[id-n].y);upd(T[i],T[i],,m,id-n,-);

            lct.link(x,i+n);lct.link(y,i+n);

        }else{

          lct.link(x,i+n);lct.link(y,i+n);

          int xx=find(x),yy=find(y);f[xx]=yy;

        }

        upd(T[i],T[i],,m,i,);

    }

    for(int i=;i<=k;++i){

        x=rd();y=rd();if(type)x^=ans,y^=ans;

        printf("%d\n",ans=n-query(T[y],,m,x,y));

    }

    return ;

}