这道题有这样一个解法：
首先把边依次加到图中，若当前这条边与图中的边形成了环，那么把这个环中最早加进来的边弹出去
并将每条边把哪条边弹了出去记录下来：ntr[i] = j，特别地，要是没有弹出边，ntr[i] = 0;
这个显然是可以用LCT来弄的对吧。
然后对于每个询问，我们的答案就是对l~r中ntr小于l的边求和，并用n减去这个值
正确性可以想一下：
如果一条边的ntr >= l,那么显然他可以与从l ~ r中的边形成环，那么它对答案没有贡献
反之如果一条边的ntr < l那么它与从l ~ r中的边是不能形成环的，那么他对答案的贡献为-1
#include<cstdio>
#include<cctype>
#include<cstring>
#define lc ch[x][0]
#define rc ch[x][1]
#include<algorithm>
using namespace std;
inline int read()
{
int x=,f=;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
}
const int maxn=;
const int maxnode=;
const int INF=;
int fa[maxn],pre[maxn],mn[maxn],val[maxn],flip[maxn],ch[maxn][];
void maintain(int x)
{
mn[x]=x;
if(val[mn[lc]]<val[mn[x]]) mn[x]=mn[lc];
if(val[mn[rc]]<val[mn[x]]) mn[x]=mn[rc];
}
void pushdown(int x)
{
if(!flip[x]) return;
flip[lc]^=;flip[rc]^=;
swap(lc,rc);flip[x]=;
}
void rotate(int x,int d)
{
pushdown(x);int y=pre[x],z=pre[y];
ch[y][d^]=ch[x][d];pre[ch[x][d]]=y;
ch[z][ch[z][]==y]=x;pre[x]=z;
ch[x][d]=y;pre[y]=x;maintain(y);
}
void splay(int x)
{
int rt=x;while(pre[rt]) rt=pre[rt];
if(rt!=x)
{
fa[x]=fa[rt];fa[rt]=;
while(pre[x]) pushdown(pre[x]),rotate(x,ch[pre[x]][]==x);
maintain(x);
}
else pushdown(x);
}
void access(int x)
{
for(int y=;x;x=fa[x])
{
splay(x);pre[ch[x][]]=;fa[ch[x][]]=x;
ch[x][]=y;pre[y]=x;fa[y]=;
maintain(x);y=x;
}
}
void makeroot(int x) {access(x);splay(x);flip[x]^=;}
void link(int x,int y){makeroot(x);fa[x]=y;}
void cut(int x,int y)
{
makeroot(x);access(y);splay(y);
pre[ch[y][]]=;ch[y][]=;maintain(y);
}
int find(int x)
{
access(x);splay(x);
while(ch[x][]) x=ch[x][];
return x;
}
int query(int x,int y)
{
makeroot(x);access(y);splay(y);
return mn[y];
}
int u[maxn],v[maxn],f[maxn],root[maxn],ToT;
int ls[maxnode],rs[maxnode],s[maxnode];
void build(int& y,int x,int l,int r,int pos)
{
s[y=++ToT]=s[x]+;if(l==r) return;
ls[y]=ls[x];rs[y]=rs[x];int mid=l+r>>;
if(pos<=mid) build(ls[y],ls[x],l,mid,pos);
else build(rs[y],rs[x],mid+,r,pos);
}
int query(int y,int l,int r,int pos)
{
if(l==r) return s[y];
int mid=l+r>>;
if(pos<=mid) return query(ls[y],l,mid,pos);
return query(rs[y],mid+,r,pos)+s[ls[y]];
}
int main()
{
int n=read(),m=read(),q=read();
for(int i=;i<=n;i++) val[i]=INF;
for(int i=;i<=m;i++)
{
u[i]=read();v[i]=read();val[i+n]=i;
if(u[i]==v[i]) {f[i]=i;continue;}
if(find(u[i])!=find(v[i])) link(u[i],i+n),link(i+n,v[i]);
else
{
int k=query(u[i],v[i]);f[i]=k-n;
cut(u[k-n],k);cut(k,v[k-n]);
link(u[i],i+n);link(i+n,v[i]);
}
}
for(int i=;i<=m;i++) build(root[i],root[i-],,m,f[i]);
while(q--)
{
int l=read(),r=read();
printf("%d\n",n-query(root[r],,m,l-)+query(root[l-],,m,l-));
}
return ;
}