GERALD07

Description

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

Input

第一行四个整数N、M、K、type，代表点数、边数、询问数以及询问是否加密。

接下来M行，代表图中的每条边。

接下来K行，每行两个整数L、R代表一组询问。对于type=0的测试点，读入的L和R即为询问的L、R；对于type=1的测试点，每组询问的L、R应为L xor lastans和R xor lastans。

Output

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

Sample Input

3 5 4 0

1 3

1 2

2 1

3 2

2 2

2 3

1 5

5 5

1 2

Sample Output

2

1

3

1

HINT

对于100%的数据，1≤N、M、K≤200,000。

连通块的个数可以用n-生成树的边数来计算。

有一个比较猎奇的做法：首先把边依次加到图中，若当前这条边与图中的边形成了环，那么把这个环中最早加进来的边弹出去，并将每条边把哪条边弹了出去记录下来：ntr[i] = j，特别地，要是没有弹出边，ntr[i] = 0;

这个可以用LCT来弄。

然后对于每个询问，我们的对l~r中ntr小于l的边计数，并用n减去这个值。

正确性可以YY一下：

• 如果一条边的ntr >= l,那么显然他可以与从l ~ r中的边形成环，那么它对答案没有贡献。
• 反之如果一条边的ntr < l那么它与从l ~ r中的边是不能形成环的，那么他对答案的贡献为-1。

对于查询从l ~ r中有多少边的ntr小于l，我反正是用的函数式线段树。时间复杂度\(O((M+K)\log N)\)。

co int N=4e5+1,M=2e5+1,INF=0x3f3f3f3f;
bool type;
int n,m,Q,lastans,top,tot,sz;
int s[N],st[M],root[M];
int c[N][2],fa[N],val[N],mn[N];
int sum[4000005],ls[4000005],rs[4000005];
bool rev[N];
struct edge{int u,v;}e[M];
bool isroot(int x){
    return c[fa[x]][0]!=x&&c[fa[x]][1]!=x;
}
void update(int x){
    int l=c[x][0],r=c[x][1];
    mn[x]=x;
    if(val[mn[l]]<val[mn[x]]) mn[x]=mn[l];
    if(val[mn[r]]<val[mn[x]]) mn[x]=mn[r];
}
void pushdown(int x){
    int l=c[x][0],r=c[x][1];
    if(rev[x]){
        std::swap(c[x][0],c[x][1]);
        rev[l]^=1,rev[r]^=1,rev[x]=0;
    }
}
void rotate(int x){
    int y=fa[x],z=fa[y],l,r;
    l=c[y][1]==x,r=l^1;
    if(!isroot(y)) c[z][c[z][1]==y]=x;
    fa[y]=x,fa[x]=z,fa[c[x][r]]=y;
    c[y][l]=c[x][r],c[x][r]=y;
    update(y),update(x);
}
void splay(int x){
    top=0,s[++top]=x;
    for(int i=x;!isroot(i);i=fa[i]) s[++top]=fa[i];
    for(int i=top;i;--i) pushdown(s[i]);
    while(!isroot(x)){
        int y=fa[x],z=fa[y];
        if(!isroot(y)) rotate(c[y][0]==x^c[z][0]==y?x:y);
        rotate(x);
    }
}
void access(int x){
    for(int t=0;x;x=fa[t=x])
        splay(x),c[x][1]=t,update(x);
}
void makeroot(int x){
    access(x),splay(x),rev[x]^=1;
}
void link(int x,int y){
    makeroot(x),fa[x]=y;
}
void cut(int x,int y){
    makeroot(x),access(y),splay(y);
    c[y][0]=fa[x]=0;
}
int find(int x){
    access(x),splay(x);
    while(c[x][0]) x=c[x][0];
    return x;
}
int query(int x,int y){
    makeroot(x),access(y),splay(y);
    return mn[y];
}
void insert(int l,int r,int x,int&y,int val){
    y=++sz;
    sum[y]=sum[x]+1;
    if(l==r) return;
    ls[y]=ls[x],rs[y]=rs[x];
    int mid=(l+r)>>1;
    if(val<=mid) insert(l,mid,ls[x],ls[y],val);
    else insert(mid+1,r,rs[x],rs[y],val);
}
int query(int l,int r,int x,int y,int val){
    if(r==val) return sum[y]-sum[x];
    int mid=(l+r)>>1;
    if(val<=mid) return query(l,mid,ls[x],ls[y],val);
    else return sum[ls[y]]-sum[ls[x]]+query(mid+1,r,rs[x],rs[y],val);

}
int main(){
//    freopen(".in","r",stdin);
//    freopen(".out","w",stdout);
    read(n),read(m),read(Q),read(type);
    val[0]=INF;
    for(int i=1;i<=n;++i) mn[i]=i,val[i]=INF;
    for(int i=1;i<=m;++i)
        read(e[i].u),read(e[i].v);
    tot=n;
    for(int i=1;i<=m;++i){
        int u=e[i].u,v=e[i].v;
        if(u==v){
            st[i]=i;continue;
        }
        if(find(u)==find(v)){
            int t=query(u,v),x=val[t];
            st[i]=x;
            cut(e[x].u,t),cut(e[x].v,t);
        }
        ++tot;
        mn[tot]=tot,val[tot]=i;
        link(u,tot),link(v,tot);
    }
    for(int i=1;i<=m;++i)
        insert(0,m,root[i-1],root[i],st[i]);
    for(int i=1;i<=Q;++i){
        int l=read<int>(),r=read<int>();
        if(type) l^=lastans,r^=lastans;
        lastans=n-query(0,m,root[l-1],root[r],l-1);
        printf("%d\n",lastans);
    }
    return 0;
}