把边的编号看成边权，维护每个状态对应的最大生成树，得到一个数组a[i],表示第i条边在这个过程中替换的是那条边，询问时看一下a[l,r]内啊有多少个小于l的算一下答案就好；代码参考：http://blog.****.net/thy_asdf/article/details/50518526
//lct不好处理边权，把一条边转成夹在两个点之间的点；
#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=,maxt=,inf=1e9;
struct edg{
int u,v;
}e[maxn];
struct node{
int l,r,v;
}tr[maxt];
int n,m,k,tot,root[maxn],a[maxn],type,lastans;
void insert(int t,int l,int r,int &x){
++tot;tr[tot]=tr[x];x=tot;
++tr[tot].v;
if(l==r)return;
int mid=l+r>>;
if(t<=mid)insert(t,l,mid,tr[x].l);
else insert(t,mid+,r,tr[x].r);
}
int qs(int x,int y,int l,int r,int L,int R){
if(r<L||l>R||l>r)return ;
if(l>=L&&r<=R)return tr[y].v-tr[x].v;
int mid=l+r>>;
return qs(tr[x].l,tr[y].l,l,mid,L,R)+qs(tr[x].r,tr[y].r,mid+,r,L,R);
}
struct node2{
int ls,rs,fa,is_root;
}tre[maxn];
int siz[maxn],mins[maxn],val[maxn],cnt,rev[maxn];
void update(int x){
mins[x]=x;
if(val[mins[tre[x].ls]]<val[mins[x]])mins[x]=mins[tre[x].ls];
if(val[mins[tre[x].rs]]<val[mins[x]])mins[x]=mins[tre[x].rs];
}
void flip(int x){swap(tre[x].ls,tre[x].rs);rev[x]^=;}
void pushdown(int x){if(rev[x])flip(tre[x].ls),flip(tre[x].rs),rev[x]^=;}
void relax(int x){if(tre[x].fa)relax(tre[x].fa);pushdown(x);}
void rx(int x){
int y=tre[x].fa,z=tre[y].fa;
tre[y].ls=tre[x].rs;
if(tre[x].rs)tre[tre[x].rs].fa=y;
tre[x].rs=y;tre[y].fa=x;
tre[x].fa=z;
if(z&&!tre[y].is_root){
if(tre[z].ls==y)tre[z].ls=x;else tre[z].rs=x;
}
if(tre[y].is_root)tre[x].is_root=,tre[y].is_root=;
update(y);update(x);
}
void lx(int x){
int y=tre[x].fa,z=tre[y].fa;
tre[y].rs=tre[x].ls;
if(tre[x].ls)tre[tre[x].ls].fa=y;
tre[x].ls=y;tre[y].fa=x;
tre[x].fa=z;
if(z&&!tre[y].is_root){
if(tre[z].ls==y)tre[z].ls=x;else tre[z].rs=x;
}
if(tre[y].is_root)tre[x].is_root=,tre[y].is_root=;
update(y);update(x);
}
void splay(int x){
relax(x);
while(!tre[x].is_root){
//cout<<"orz"<<endl;
int y=tre[x].fa,z=tre[y].fa;
if(tre[y].is_root){if(tre[y].ls==x)rx(x);else lx(x);}
else{
if(tre[z].ls==y&&tre[y].ls==x){rx(y);rx(x);}
else if(tre[z].ls==y&&tre[y].rs==x){lx(x);rx(x);}
else if(tre[z].rs==y&&tre[y].ls==x){rx(x);lx(x);}
else {lx(y);lx(x);}
}
}
}
void ace(int x){
int y=;
do{
splay(x);
if(tre[x].rs)tre[tre[x].rs].is_root=;
tre[tre[x].rs=y].is_root=;
update(x);
x=tre[y=x].fa;
}while(x);
}
void makeroot(int x){ace(x);splay(x);flip(x);}
void link(int x,int y){makeroot(x);tre[x].fa=y;}
void cut(int x,int y){makeroot(x);ace(y);splay(y);tre[y].ls=tre[x].fa=;tre[x].is_root=;}//一开始最后这句话丢了；
int findrt(int x){ace(x);splay(x);for(;tre[x].ls;x=tre[x].ls);return x;}
int query(int x,int y){makeroot(x);ace(y);splay(y);return mins[y];}
void pre(){
for(int i=;i<=n+m;++i)tre[i].is_root=;
cnt=n;
for(int i=;i<=m;++i){
int u=e[i].u,v=e[i].v;
if(u==v){a[i]=i;continue;}
if(findrt(u)==findrt(v)){
int cp=query(u,v),x=val[cp];
a[i]=x;cut(e[x].u,cp);cut(e[x].v,cp);
}
++cnt;mins[cnt]=cnt;val[cnt]=i;link(u,cnt);link(v,cnt);
}
for(int i=;i<=m;++i){
root[i]=root[i-];insert(a[i],,m,root[i]);
}
}
int main(){
cin>>n>>m>>k>>type;
val[]=inf;
for(int i=;i<=n;++i)mins[i]=i,val[i]=inf;
for(int i=;i<=m;++i)scanf("%d%d",&e[i].u,&e[i].v);
pre();
int l,r;
for(int i=;i<=k;++i){
scanf("%d%d",&l,&r);
if(type)l^=lastans,r^=lastans;
printf("%d\n",lastans=(n-qs(root[l-],root[r],,m,,l-)));
}
return ;
}