#include <bits/stdc++.h>

#define N 400005

#define inf 1000000000

#define setIO(s) freopen(s".in","r",stdin) , freopen(s".out","w",stdout)

using namespace std;

int rt[N];

struct Edge

{

    int u,v,c;

    Edge(int u=0,int v=0,int c=0):u(u),v(v),c(c){}

}e[N];

struct Union_Find_set

{

    int p[N];

    void init()

    {

        for(int i=0;i<N;++i) p[i]=i;

    }

    int find(int x)

    {

        return p[x]==x?x:p[x]=find(p[x]);

    }

    int merge(int x,int y)

    {

        x=find(x),y=find(y);

        if(x!=y)

        {

            p[x]=y;

            return 1;

        }

        else

        {

            return 0;

        }

    }

}ufs;

struct Link_Cut_Tree

{

    #define lson t[x].ch[0]

    #define rson t[x].ch[1]

    int sta[N];

    struct Node

    {

        int ch[2],f,min,id,val,rev;

    }t[N];

    int get(int x)

    {

        return t[t[x].f].ch[1]==x;

    }

    int isrt(int x)

    {

        return !(t[t[x].f].ch[0]==x||t[t[x].f].ch[1]==x);

    }

    void pushup(int x)

    {

        t[x].min=t[x].val,t[x].id=x;

        if(lson&&t[lson].min<t[x].min) t[x].min=t[lson].min,t[x].id=t[lson].id;

        if(rson&&t[rson].min<t[x].min) t[x].min=t[rson].min,t[x].id=t[rson].id;

    }

    void mark(int x)

    {

        if(x) t[x].rev^=1,swap(lson,rson);

    }

    void pushdown(int x)

    {

        if(x&&t[x].rev)

        {

            t[x].rev=0;

            if(lson) mark(lson);

            if(rson) mark(rson);

        }

    }

    void rotate(int x)

    {

        int old=t[x].f,fold=t[old].f,which=get(x);

        if(!isrt(old)) t[fold].ch[t[fold].ch[1]==old]=x;

        t[old].ch[which]=t[x].ch[which^1],t[t[old].ch[which]].f=old;

        t[x].ch[which^1]=old,t[old].f=x,t[x].f=fold;

        pushup(old),pushup(x);

    }

    void splay(int x)

    {

        int v=0,u=x,fa;

        for(sta[++v]=u;!isrt(u);u=t[u].f) sta[++v]=t[u].f;

        for(;v;--v) pushdown(sta[v]);

        for(u=t[u].f;(fa=t[x].f)!=u;rotate(x))

            if(t[fa].f!=u)

                rotate(get(fa)==get(x)?fa:x);

    }

    void Access(int x)

    {

        for(int y=0;x;y=x,x=t[x].f)

            splay(x),rson=y,pushup(x);

    }

    void makeroot(int x)

    {

        Access(x),splay(x),mark(x);

    }

    void split(int x,int y)

    {

        makeroot(x),Access(y),splay(y);

    }

    void link(int x,int y)

    {

        makeroot(x),t[x].f=y;

    }

    void cut(int x,int y)

    {

        makeroot(x),Access(y),splay(y);

        t[y].ch[0]=t[x].f=0;

        pushup(y);

    }

    #undef lson

    #undef rson

}lct;

struct Segment_Tree

{

    int tot;

    int lson[N*20],rson[N*20],sum[N*20];

    int update(int x,int l,int r,int p,int d)

    {

        int oo=++tot;

        lson[oo]=lson[x],rson[oo]=rson[x],sum[oo]=sum[x]+d;

        if(l==r) return oo;

        int mid=(l+r)>>1;

        if(p<=mid) lson[oo]=update(lson[x],l,mid,p,d);

        else rson[oo]=update(rson[x],mid+1,r,p,d);

        return oo;

    }

    int query(int x,int l,int r,int L,int R)

    {

        if(!x) return 0;

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

        int mid=(l+r)>>1,re=0;

        if(L<=mid) re+=query(lson[x],l,mid,L,R);

        if(R>mid)  re+=query(rson[x],mid+1,r,L,R);

        return re;

    }

}tr;

int main()

{

    // setIO("input");

    int n,m,i,j,k,ty;

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

    lct.t[0].val=inf;

    for(i=1;i<=n;++i) lct.t[i].val=inf,lct.pushup(i);

    ufs.init();

    for(i=1;i<=m;++i)

    {

        scanf("%d%d",&e[i].u,&e[i].v);

        int u=e[i].u;

        int v=e[i].v;

        int _new=i+n;

        rt[i]=rt[i-1];

        if(u==v)

        {

            continue;

        }

        rt[i]=tr.update(rt[i-1],1,m,i,1);

        if(ufs.merge(u,v))

        {

            lct.t[_new].val=i;

            lct.pushup(_new);

            lct.link(u,_new);

            lct.link(_new,v);

        }

        else

        {

            lct.split(u,v);

            int cc=lct.t[v].id;

            lct.cut(cc, e[cc-n].u);

            lct.cut(cc, e[cc-n].v);

            rt[i]=tr.update(rt[i],1,m,cc-n,-1);

            lct.t[_new].val=i;

            lct.pushup(_new);

            lct.link(_new, u);

            lct.link(_new, v);

        }

    }

    int lastans=0;

    for(i=1;i<=k;++i)

    {

        int l,r;

        scanf("%d%d",&l,&r);

        if(ty)

        {

            l^=lastans;

            r^=lastans;

            if(l>r) swap(l,r);

        }

        lastans=n-tr.query(rt[r],1,m,l,r);

        printf("%d\n",lastans);

    }

    return 0;

}