记录编号	417065	评测结果	AAAAAAAAAA
题目名称	[AHOI 2005] LANE 航线规划	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.270 s
提交时间	2017-06-23 23:50:31	内存使用	16.33 MiB

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int N=2e5+10;
int n,m,w[N],head[N],next[N];
bool vis[N];
void add(int f,int t){
	static int cnt=1;
	w[++cnt]=t;
	next[cnt]=head[f];
	head[f]=cnt;
}
int fa[N],S[N];
int find(int x){return x==S[x]?x:S[x]=find(S[x]);}
void dfs(int x){
	for (int i=head[x];i;i=next[i])
	if (!vis[i]){
		vis[i]=vis[i^1]=1;
		int v=w[i];
		if (fa[v]){
			for (int i=x;i!=v;i=fa[i]){
				int y=find(i);
				if (y==find(v)) break;
				S[y]=find(v);
				i=y;
			}
		}
		else fa[v]=x,dfs(v);
	}
}
struct opt{int tp,x,y;}Q[N];
int son[N][2],val[N],sum[N];
bool root[N],rev[N],tag[N];
#define lc son[x][0]
#define rc son[x][1]
void update(int x){
	sum[x]=val[x]+sum[lc]+sum[rc];
}
void clear(int x){
	sum[x]=val[x]=0;
	tag[x]=1;
}
void flip(int x){
	swap(lc,rc);
	rev[x]^=1;
}
void pushdown(int x){
	if (!x) return;
	if (tag[x]){
		if (lc) clear(lc);
		if (rc) clear(rc);
		tag[x]=0;
	}
	if (rev[x]){
		if (lc) flip(lc);
		if (rc) flip(rc);
		rev[x]=0;
	}
}
void rot(int x){
	int y=fa[x],z=fa[y];
	bool b=(x==son[y][1]);
	fa[son[y][b]=son[x][!b]]=y;
	fa[son[x][!b]=y]=x;
	fa[x]=z;
	if (y==son[z][0]) son[z][0]=x;else
	if (y==son[z][1]) son[z][1]=x;
	root[x]=root[y];root[y]=0;
	update(y);update(x);
}
void splay(int x){
	pushdown(x);
	for (;!root[x];rot(x)){
		int y=fa[x],z=fa[y];
		pushdown(z);pushdown(y);pushdown(x);
		if (!root[y]) rot((x==son[y][0])==(y==son[z][0])?y:x); 
	}
}
void access(int x){
	splay(x);
	root[rc]=1;rc=0;
	update(x);
	while (fa[x]){
		int y=fa[x];
		splay(y);
		root[son[y][1]]=1;
		root[son[y][1]=x]=0;
		update(y);
		splay(x);
	}
}
void makeroot(int x){
	access(x);
	flip(x);
}
typedef pair<int,int> pii;
int q,M,id,ans[N];
pii eg[N],dl[N];
vector<int> E[N];
void DFS(int x){
	for (int i=0;i<E[x].size();i++){
		int v=E[x][i];
		if (fa[v]) continue;
		fa[fa[v]=++id]=x;
		sum[id]=val[id]=1;
		DFS(v);
	}
}
int main()
{
	freopen("lane.in","r",stdin);
	freopen("lane.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (int i=1;i<=m;i++){
		scanf("%d%d",&eg[i].first,&eg[i].second);
		if (eg[i].first>eg[i].second)
			swap(eg[i].first,eg[i].second);
	}
	while (1){
		scanf("%d",&Q[q+1].tp);
		if (Q[q+1].tp==-1) break;
		q++;
		scanf("%d%d",&Q[q].x,&Q[q].y);
		if (Q[q].x>Q[q].y) swap(Q[q].x,Q[q].y);
		if (!Q[q].tp) dl[++M]=pii(Q[q].x,Q[q].y);
	}
	sort(eg+1,eg+m+1);
	sort(dl+1,dl+M+1);
	for (int i=1,p=1;i<=m;i++)
	if (eg[i]==dl[p]) p++;
	else{
		add(eg[i].first,eg[i].second);
		add(eg[i].second,eg[i].first);
	}
	for (int i=1;i<=n;i++) S[i]=i; 
	fa[1]=1;dfs(1);
	for (int x=1;x<=n;x++)
	for (int i=head[x];i;i=next[i]){
		int v=find(x),u=find(w[i]);
		if (v!=u) E[v].push_back(u);
	}
	for (int i=1;i<=n;i++) fa[i]=0; 
	id=n;fa[1]=1;DFS(1);fa[1]=0;
	for (int i=1;i<=id;i++) root[i]=1;
	for (int i=q;i;i--){
		int x=find(Q[i].x),y=find(Q[i].y); 
		makeroot(x);
		access(y);
		if (Q[i].tp==1) ans[i]=sum[y];
			else clear(y);
	}
	for (int i=1;i<=q;i++)
		if (Q[i].tp==1) printf("%d\n",ans[i]); 
	return 0;
}