```cpp
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<set>
#include<vector>
#include<queue>
#include<stack>
#include<cstring>
#include<cstdlib>
#include<map>
#include<ctime>
#define rep(i,a,b) for(register int i=a;i<=b;++i)
#define rev(i,a,b) for(register int i=a;i>=b;--i)
#define gra(i,u) for(register int i=head[u];i;i=edge[i].nxt)
#define Clear(a) memset(a,0,sizeof(a))
#define yes puts("YES")
#define no puts("NO")
using namespace std;
typedef long long ll;
const int INF(1e9+10);
const ll LLINF(1e18+10);
inline int read()
{
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9')s=s*10+(ch-'0'),ch=getchar();
return s*w;
}
template<typename T>
inline T Min(T x,T y){return x<y?x:y;}
template<typename T>
inline T Max(T x,T y){return x>y?x:y;}
template<typename T>
inline void Swap(T&x,T&y){T t=x;x=y;y=t;return;}
template<typename T>
inline T Abs(T x){return x<0?-x:x;}
const int MAXN(4e5+10);
int n,m,q;
struct E{int u,v;};
E edge[MAXN<<1];
struct node{int opt,u,v;};
node a[MAXN];
struct Union_Find_Set
{
int par[MAXN],rankk[MAXN];
inline void init_()
{
rep(i,1,n+m+q+Max(n,Max(m,q))) par[i]=i;
return;
}
inline int find(int x){return par[x]==x?x:par[x]=find(par[x]);}
inline void unite(int x,int y)
{
x=find(x),y=find(y);
par[x]=y;
return;
}
inline bool same(int x,int y){return find(x)==find(y);}
};
Union_Find_Set dsu;
struct LCT
{
int ch[MAXN][2],fa[MAXN],siz[MAXN],st[MAXN],tp,val[MAXN];
bool tag[MAXN],zero[MAXN];
int num,qurundong;
inline void push_up(int u)
{
if(!ch[u][0]) siz[ch[u][0]]=0;
if(!ch[u][1]) siz[ch[u][1]]=0;
siz[u]=siz[ch[u][0]]+siz[ch[u][1]]+val[u];
return;
}
inline void lazy_tag(int u)
{
Swap(ch[u][0],ch[u][1]);
tag[u]^=1;
return;
}
inline void push_down(int u)
{
if(tag[u])
{
if(ch[u][0]) lazy_tag(ch[u][0]);
if(ch[u][1]) lazy_tag(ch[u][1]);
tag[u]=false;
}
return;
}
inline bool isroot(int u){return u!=ch[fa[u]][0]&&u!=ch[fa[u]][1];}
inline bool Get(int x){return x==ch[fa[x]][1];}
inline void update(int x)
{
if(!isroot(x)) update(fa[x]);
push_down(x);
return;
}
inline void rotate(int x)
{
int y=fa[x],z=fa[y],chk=Get(x);
if(!isroot(y)) ch[z][Get(y)]=x;
ch[y][chk]=ch[x][!chk],fa[ch[x][!chk]]=y;
ch[x][!chk]=y,fa[y]=x,fa[x]=z;
push_up(y);
push_up(x);
return;
}
inline void splay(int x)
{
update(x);
for(register int f=0;f=fa[x],!isroot(x);rotate(x))
if(!isroot(f)) rotate(Get(f)==Get(x)?f:x);
return;
}
inline void access(int x)
{
for(register int p=0;x;p=x,x=fa[x])
{
splay(x);
ch[x][1]=p;
push_up(x);
}
return;
}
inline void makeroot(int x)
{
access(x);
splay(x);
lazy_tag(x);
return;
}
inline int findroot(int x)
{
access(x);
splay(x);
push_down(x);
while(ch[x][0]) x=ch[x][0],push_down(x);
return x;
}
inline bool same(int x,int y){return findroot(x)==findroot(y);}
inline void Link(int x,int y)
{
if(!same(x,y)) makeroot(x),fa[x]=y;
return;
}
inline void cut(int x,int y)
{
makeroot(x);
access(y);
splay(y);
if(ch[y][0]==x&&!ch[x][1]) ch[y][0]=fa[x]=0;
push_up(y);
return;
}
inline void split(int x,int y)
{
makeroot(x);
access(y);
splay(y);
return;
}
inline void add_edge(int u,int v,int w)
{
// printf("add : %d %d %d\n",u,v,w);
++qurundong;
val[qurundong]=w;
Link(u,qurundong);
Link(qurundong,v);
return;
}
inline void print(int u)
{
if(ch[u][0]) print(ch[u][0]);
st[++tp]=u;
if(ch[u][1]) print(ch[u][1]);
return;
}
inline void solve(int u,int v)
{
split(u,v);
tp=0;
print(v);
// puts("seq:");
// rep(i,1,tp) printf("%d ",st[i]);
// puts("");
// printf("qurundong:%d\n",qurundong);
rep(i,1,tp-1)
{
cut(st[i],st[i+1]);
dsu.unite(st[i+1],qurundong+1);
}
dsu.unite(st[1],qurundong+1);
add_edge(u,v,0);
}
};
LCT lct;
int ans[MAXN];
bool vis[MAXN];
typedef pair<int,int> P;
map<P,int>mp;
inline void input()
{
n=read(),m=read();
lct.num=n;
rep(i,1,m) edge[i].u=read(),edge[i].v=read();
rep(i,1,m)
{
P p=make_pair(edge[i].u,edge[i].v);
mp[p]=i;
}
a[++q].opt=read();
while(a[q].opt!=-1)
{
a[q].u=read(),a[q].v=read();
a[++q].opt=read();
}
--q;
reverse(a+1,a+1+q);
lct.qurundong=n+m+q;
dsu.init_();
return;
}
inline void work()
{
rep(i,1,q)
{
int opt=a[i].opt,u=a[i].u,v=a[i].v;
if(opt==0)
{
int p=mp[make_pair(u,v)];
vis[p]=true;
}
}
rep(i,1,m)
{
if(!vis[i])
{
int u=edge[i].u,v=edge[i].v;
if(u==v) continue;
u=dsu.find(u),v=dsu.find(v);
if(!lct.same(u,v)) lct.add_edge(u,v,1);
else
{
lct.split(u,v);
lct.solve(u,v);
}
}
}
rep(i,1,q)
{
int opt=a[i].opt,u=a[i].u,v=a[i].v;
u=dsu.find(u),v=dsu.find(v);
if(opt==1)
{
if(!lct.same(u,v)) ans[i]=0;
else
{
lct.split(u,v);
ans[i]=lct.siz[v];
}
}
else
{
if(!lct.same(u,v)) lct.add_edge(u,v,1);
else
{
lct.split(u,v);
lct.solve(u,v);
}
}
}
rev(i,q,1) if(a[i].opt==1) printf("%d\n",ans[i]);
return;
}
int main()
{
// freopen("read.txt","r",stdin);
input();
work();
return 0;
}
/*
Date : 2022/8/29
Author : UperFicial
Start coding at : 17:39
finish debugging at :
*/
```
by UperFicial @ 2022-08-29 21:04:00