文件详细信息

下载本文件

本文件的大小为 2065 字节。

#include<algorithm>
#include<cstdio>
namespace IO{
	const int ARR_SIZE=1<<24;
	#define gc() ((IO::si!=IO::ti||(IO::ti=(IO::si=IO::input)+fread(IO::input,1,IO::ARR_SIZE,stdin))),*(IO::si++))
	#define pc(ch) ((IO::o.so!=IO::o.to||(fwrite(IO::o.output,1,IO::ARR_SIZE,stdout),IO::o.so=IO::o.output)),*(IO::o.so++)=ch)
	char input[ARR_SIZE],*si=input,*ti=input;
	struct Output_Stream{
		char output[ARR_SIZE],*so=output,*to=output+ARR_SIZE;
		~Output_Stream(){
			if(so==output)return;
			fwrite(output,1,so-output,stdout);
			so=output;
		}
	}o;
	template<typename T>
	void read(T&num){
		int ch=gc();
		num=0;
		while(ch<48||ch>57)ch=gc();
		while(ch>=48&&ch<=57)num=(num<<3)+(num<<1)+(ch^48),ch=gc();
	}
	void getstr(char*str){
		char ch=gc();
		while(ch=='\r'||ch=='\n'||ch==' '||ch=='\t')ch=gc();
		while(ch!='\r'&&ch!='\n'&&ch!=' '&&ch!='\t')*(str++)=ch,ch=gc();
	}
	template<typename T>
	void write(T a){
		static int ch[50],cnt;
		if(a==0)pc('0');
		cnt=0;
		while(a)ch[++cnt]=a%10|48,a/=10;
		while(cnt)pc(ch[cnt--]);
	}
	void putstr(char*str){
		while(*str!='\0')pc(*(str++));
	}
}
using IO::read;
using IO::getstr;
using IO::write;
using IO::putstr;
template<typename T>
T max(T a,T b){
	return a>b?a:b;
}
const int maxn=500005;
int n,m,dep[maxn],fa[maxn],size[maxn],val[maxn],ans;
int find(int a){
	while(a!=fa[a])a=fa[a];
	return a;
}
int cnt;
void merge(int u,int v){
	u=find(u),v=find(v);
	cnt++;
	if(u==v)return;
	if(size[u]<size[v])std::swap(u,v);
	fa[v]=u,size[u]+=size[v],val[v]=cnt;
}
void init(int u){
	if(u==fa[u])return;
	init(fa[u]);
	dep[u]=dep[fa[u]]+1;
}
int main(){
	read(n),read(m);
	for(int i=1;i<=n;i++)fa[i]=i,size[i]=1;
	int opt,u,v;
	for(int i=1;i<=m;i++){
		read(opt),read(u),read(v);
		u^=ans,v^=ans;
		if(opt==0)merge(u,v);
		else{
			int fu=find(u),fv=find(v);
			if(fu!=fv)ans=0;
			else{
				init(u),init(v);
				ans=0;
				if(dep[u]<dep[v])std::swap(u,v);
				while(dep[u]>dep[v])ans=max(ans,val[u]),u=fa[u];
				while(u!=v)ans=max(ans,val[u]),u=fa[u],ans=max(ans,val[v]),v=fa[v];
			}
			write(ans),pc('\n');
		}
	}
	return 0;
}