题解：
还是比较简单的
首先我们的思路是 确定起点 然后之后贪心的选择边（也就是越靠前越希望选）
我们发现我们只需要将起点从后向前枚举
然后用lct维护连通性
因为强制在线，所以用主席树记录状态就可以了
*数组开小查了很久
代码：
#include <bits/stdc++.h>
using namespace std;
#define IL inline
#define rint register int
#define rep(i,h,t) for (rint i=h;i<=t;i++)
#define dep(i,t,h) for (rint i=t;i>=h;i--)
const int INF=1e9;
const int N=4e5+;
char ss[<<],*A=ss,*B=ss;
IL char gc()
{
return A==B&&(B=(A=ss)+fread(ss,,<<,stdin),A==B)?EOF:*A++;
}
template<class T> void read(T &x)
{
rint f=,c; while (c=gc(),c<||c>) if (c=='-') f=-; x=c^;
while (c=gc(),<c&&c<) x=(x<<)+(x<<)+(c^); x*=f;
}
int data[N],ls[N],rs[N],fa[N],v[N];
bool rev[N];
IL void updata(int x)
{
data[x]=min(min(data[ls[x]],data[rs[x]]),v[x]);
}
IL void down(int x)
{
if (!rev[x]) return;
rev[ls[x]]^=; rev[rs[x]]^=;
swap(ls[x],rs[x]);
rev[x]=;
}
IL bool pd(int x)
{
int fa1=fa[x];
if (ls[fa1]!=x&&rs[fa1]!=x) return();
else return();
}
void rotate(int x,int y)
{
int fa1=fa[x];
if (y==)
{
rs[fa1]=ls[x];
if (ls[x]) fa[ls[x]]=fa1;
} else
{
ls[fa1]=rs[x];
if (rs[x]) fa[rs[x]]=fa1;
}
fa[x]=fa[fa1];
if (pd(fa1))
{
if (ls[fa[fa1]]==fa1) ls[fa[fa1]]=x; else rs[fa[fa1]]=x;
}
fa[fa1]=x;
if (y==) ls[x]=fa1; else rs[x]=fa1;
updata(fa1); updata(x);
}
void dfs(int x)
{
if (pd(x)) dfs(fa[x]);
down(x);
}
void splay(int x)
{
dfs(x);
int fa1=fa[x];
while (pd(x))
{
if (!pd(fa1))
{
if (x==ls[fa1]) rotate(x,); else rotate(x,);
} else
if (ls[fa[fa1]]==fa1)
if (ls[fa1]==x)
rotate(fa1,),rotate(x,);
else
rotate(x,),rotate(x,);
else
if (rs[fa1]==x)
rotate(fa1,),rotate(x,);
else
rotate(x,),rotate(x,);
fa1=fa[x];
}
}
void access(int x)
{
for (int y=;x;y=x,x=fa[x])
{
splay(x); rs[x]=y; updata(x);
}
}
int fdr(int x)
{
access(x);
splay(x);
while (ls[x]) x=ls[x];
return(x);
}
void mkr(int x)
{
access(x);
splay(x);
rev[x]^=;
}
void split(int x,int y)
{
mkr(x);
access(y);
splay(y);
}
void link(int x,int y)
{
mkr(x);
access(y);
splay(y);
fa[x]=y;
}
void cut(int x,int y)
{
mkr(x);
access(y);
splay(y);
ls[y]=fa[x]=;
updata(y);
}
#define mid ((h+t)/2)
int root[N],jl1[N],jl2[N];
struct segtment{
int p[N*],ls[N*],rs[N*],cnt;
segtment() { cnt=; }
void updata(int x)
{
p[x]=p[ls[x]]+p[rs[x]];
}
void change(int last,int &x,int h,int t,int pos,int k)
{
x=++cnt; ls[x]=ls[last]; rs[x]=rs[last];
p[x]=p[last]+k;
if (h==t) return;
if (pos<=mid) change(ls[last],ls[x],h,mid,pos,k);
else change(rs[last],rs[x],mid+,t,pos,k);
updata(x);
}
int query(int x,int h,int t,int h1,int t1)
{
if (h1<=h&&t<=t1) return(p[x]);
int ans=;
if (h1<=mid) ans+=query(ls[x],h,mid,h1,t1);
if (mid<t1) ans+=query(rs[x],mid+,t,h1,t1);
return(ans);
}
}S;
int n,m,k,type;
int main()
{
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
read(n); read(m); read(k); read(type);
int ans=;
data[]=v[]=INF;
rep(i,,n) v[i]=INF,v[i+n]=i;
rep(i,,m)v[i+n]=i;
int p=,maxn=;
rep(i,,m)
{
// cout<<i<<endl;
int x,y;
root[i]=root[i-];
read(x); read(y);
if (x==y) continue;
jl1[i]=x;jl2[i]=y;
mkr(y);
if (fdr(x)==y)
{
split(x,y);
int x1=data[y];
cut(x1+n,jl1[x1]);
cut(x1+n,jl2[x1]);
S.change(root[i],root[i],,m,x1,-);
p--;
}
p++;
link(i+n,x);
link(i+n,y);
S.change(root[i],root[i],,m,i,);
if (p>n) return ;
maxn=max(maxn,p);
}
rep(i,,k)
{
int x,y;
read(x); read(y);
if (type) x^=ans,y^=ans;
printf("%d\n",ans=n-S.query(root[y],,m,x,y));
}
return ;
}