N个点M条边的无向图，询问保留图中编号在[l,r]的边的时候图中的联通块个数。

第一行四个整数N、M、K、type，代表点数、边数、询问数以及询问是否加密。
接下来M行，代表图中的每条边。
接下来K行，每行两个整数L、R代表一组询问。对于type=0的测试点，读入的L和R即为询问的L、R；对于type=1的测试点，每组询问的L、R应为L xor lastans和R xor lastans。

K行每行一个整数代表该组询问的联通块个数。

3 5 4 0
1 3
1 2
2 1
3 2
2 2
2 3
1 5
5 5
1 2

2
1
3
1

//by 减维

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

#include<bitset>

#include<set>

#include<cmath>

#include<vector>

#include<set>

#include<map>

#include<ctime>

#include<algorithm>

#define ll long long

#define il inline

#define rg register

#define db double

#define inf (1<<30)

#define maxn 400005

#define mpr make_pair

#define eps 1e-8

using namespace std;

inline int read()

{

    int ret=;bool fla=;char ch=getchar();

    while((ch<''||ch>'')&&ch!='-')ch=getchar();

    if(ch=='-'){fla=;ch=getchar();}

    while(ch>=''&&ch<=''){ret=ret*+ch-'';ch=getchar();}

    return fla?-ret:ret;

}

struct edge{

    int x,y;

}e[maxn];

struct tree{

    int l,r,v;

}t[maxn<<];

int n,m,q,tt,ans,cnt,rt[maxn],fa[maxn],son[maxn][],val[maxn],rev[maxn],pos[maxn],tim[maxn];

il bool pdp(int x){return son[fa[x]][]==x;}

il bool isrt(int x){return son[fa[x]][]!=x&&son[fa[x]][]!=x;}

il void rever(int x){rev[x]^=;swap(son[x][],son[x][]);}

il void upda(int x)

{

    pos[x]=x;

    if(son[x][]&&val[pos[son[x][]]]<val[pos[x]]) pos[x]=pos[son[x][]];

    if(son[x][]&&val[pos[son[x][]]]<val[pos[x]]) pos[x]=pos[son[x][]];

}

il void pdn(int x)

{

    if(rev[x])

    {

        if(son[x][]) rever(son[x][]);

        if(son[x][]) rever(son[x][]);

        rev[x]=;

    }

}

void pd(int x){if(!isrt(x)) pd(fa[x]);pdn(x);}

il void rot(int x)

{

    int f=fa[x],g=fa[f],o=pdp(x);

    if(!isrt(f)) son[g][pdp(f)]=x;fa[x]=g;

    son[f][o]=son[x][!o];fa[son[f][o]]=f;

    son[x][!o]=f;fa[f]=x;

    upda(f),upda(x);

}

il void splay(int x)

{

    pd(x);

    for(;!isrt(x);rot(x))

        if(!isrt(fa[x])) rot(pdp(fa[x])==pdp(x)?fa[x]:x);

}

il void acc(int x)

{

    for(int y=;x;y=x,x=fa[x])

        splay(x),son[x][]=y,upda(x);

}

il int find(int x)

{

    acc(x);splay(x);

    while(son[x][]) pd(x),x=son[x][];

    return x;

}

il void bert(int x){acc(x);splay(x);rever(x);}

il void spli(int x,int y){bert(x);acc(y);splay(y);}

il void cut(int x,int y){spli(x,y);fa[x]=son[y][]=;upda(y);}

il void link(int x,int y,int z)

{

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

    {

        spli(x,y);

        int aa=pos[y];//printf("%d\n",aa);

        cut(e[aa-n].x,aa);cut(e[aa-n].y,aa);

        tim[aa-n]=z-n;

    }

    bert(x);fa[x]=z;

    bert(y);fa[y]=z;

}

void upd(int x)

{

    t[x].v=t[t[x].l].v+t[t[x].r].v;

}

void build(int l,int r,int las,int &now,int v)

{

    now=++cnt;t[now]=t[las];t[now].v++;

    if(l==r)return ;

    int mid=(l+r)>>;

    if(v<=mid) build(l,mid,t[las].l,t[now].l,v);

    else build(mid+,r,t[las].r,t[now].r,v);

}

int query(int l,int r,int x,int y,int v)

{

    if(l==v) return t[y].v-t[x].v;

    int mid=(l+r)>>;

    if(v<=mid) return query(l,mid,t[x].l,t[y].l,v)+t[t[y].r].v-t[t[x].r].v;

    else return query(mid+,r,t[x].r,t[y].r,v);

}

int main()

{

    n=read(),m=read();q=read(),tt=read();

    for(int i=;i<=n;++i) val[i]=inf;

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

    {

        e[i].x=read(),e[i].y=read();

        val[n+i]=i;tim[i]=m+;

        if(e[i].x==e[i].y){tim[i]=i;continue;}

        link(e[i].x,e[i].y,n+i);

    }

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

        build(,m+,rt[i-],rt[i],tim[i]);

    for(int i=,l,r;i<=q;++i)

    {

        l=read(),r=read();

        if(tt) l^=ans,r^=ans;

        printf("%d\n",ans=n-query(,m+,rt[l-],rt[r],r+));

    }

    return ;

}