首先最远点一定是直径的端点。

然后连边想到 LCT，直接暴力枚举维护两棵树合并后的直径。

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+10;
#define lc(p) tr[p].ch[0]
#define rc(p) tr[p].ch[1]
#define fa(p) tr[p].f
struct node{int ch[2],f,s,v,tag;}tr[N];
bool notrt(int p){return lc(fa(p))==p||rc(fa(p))==p;}
void pushup(int p){tr[p].s=tr[lc(p)].s+tr[rc(p)].s+tr[p].v;}
void pushdown(int p)
{
	if(tr[p].tag)
	{
		swap(lc(p),rc(p));
		tr[lc(p)].tag^=1;tr[rc(p)].tag^=1;
		tr[p].tag=0;
	}
} 
void pushall(int p)
{
	if(notrt(p))pushall(fa(p));
	pushdown(p);
}
void rotate(int x)
{
	int y=fa(x),z=fa(y),k=rc(y)==x;
	if(notrt(y))tr[z].ch[rc(z)==y]=x;fa(x)=z;
	tr[y].ch[k]=tr[x].ch[k^1],fa(tr[x].ch[k^1])=y;
	tr[x].ch[k^1]=y;fa(y)=x;
	pushup(y);pushup(x);
}
void splay(int x)
{
	pushall(x);
	while(notrt(x))
	{
		int y=fa(x),z=fa(y);
		if(notrt(y))((rc(y)==x)^(rc(z)==y))?rotate(x):rotate(y);
		rotate(x);
	}
}
void access(int x)
{
	for(int y=0;x;)
	{
		splay(x);
		rc(x)=y;
		pushup(x);
		y=x;x=fa(x);
	}
}
void makert(int x)
{
	access(x);
	splay(x);
	tr[x].tag^=1;
}
void split(int x,int y)
{
	makert(x);
	access(y);
	splay(y);
}
void link(int x,int y)
{
	makert(x);
	fa(x)=y;
}
void cut(int x,int y)
{
	split(x,y);
	fa(x)=lc(y)=0;
}
struct dsu
{
	int fa[N];
	int findfa(int x){return fa[x]==x?fa[x]:fa[x]=findfa(fa[x]);}
}dtr;
int d1[N],d2[N];
void merge(int x,int y)
{
	int tx=dtr.findfa(x),ty=dtr.findfa(y);
	vector<int>a={d1[tx],d1[ty],d2[tx],d2[ty]};
	int res1=0,res2=0,mx=0;
	link(x,y);
	for(int i=0;i<4;i++)for(int j=i+1;j<4;j++)
	{
		split(a[i],a[j]);
		if(tr[a[j]].s>mx)
		{
			mx=tr[a[j]].s;
			res1=a[i],res2=a[j];
		}
	}
	
	dtr.fa[tx]=ty;d1[ty]=res1,d2[ty]=res2;
}
signed main()
{
	int opt;cin>>opt;
	int n,q,lst=0;cin>>n>>q;
	for(int i=1;i<=n;i++)dtr.fa[i]=i,d1[i]=d2[i]=i,tr[i].v=1;
	while(q--)
	{
		int op,x,y;cin>>op;
		if(op==1)
		{
			cin>>x>>y;x^=(lst*opt),y^=(lst*opt);
			merge(x,y);
		}
		else
		{
			cin>>x;x^=(lst*opt);int tx=dtr.findfa(x),ans=0;
			split(d1[tx],x);
			ans=max(ans,tr[x].s-1);
			split(d2[tx],x);
			ans=max(ans,tr[x].s-1);
			cout<<ans<<'\n';
			lst=ans;
		}
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;

const int Maxn = 300010;
int Father[ Maxn ], Child[ Maxn ][ 2 ], Stack[ Maxn ], Tag[ Maxn ];
int Size[ Maxn ];
int N, Q, Rec[ Maxn ][ 2 ], Fa[ Maxn ], Type;

void Collect( int Ind ) {
	Size[ Ind ] = Size[ Child[ Ind ][ 0 ] ] + Size[ Child[ Ind ][ 1 ] ] + 1;
	return;
}
void TagOn( int Ind ) {
	Tag[ Ind ] ^= 1;
	swap( Child[ Ind ][ 0 ], Child[ Ind ][ 1 ] );
	return;
}
void TagDown( int Ind ) {
	if( Tag[ Ind ] ) {
		TagOn( Child[ Ind ][ 0 ] );
		TagOn( Child[ Ind ][ 1 ] );
		Tag[ Ind ] ^= 1;
	}
	return;
}
bool IsRoot( int Ind ) {
	if( Ind == 0 ) return true;
	return !( ( Child[ Father[ Ind ] ][ 0 ] == Ind ) || ( Child[ Father[ Ind ] ][ 1 ] == Ind ) );
}
void Rotate( int C ) {
	int B = Father[ C ];
	int A = Father[ B ];
	int Tag = Child[ B ][ 1 ] == C;
	if( !IsRoot( B ) ) Child[ A ][ Child[ A ][ 1 ] == B ] = C;
	Father[ C ] = A;
	Child[ B ][ Tag ] = Child[ C ][ Tag ^ 1 ];
	Father[ Child[ C ][ Tag ^ 1 ] ] = B;
	Child[ C ][ Tag ^ 1 ] = B;
	Father[ B ] = C;
	Collect( B ); Collect( C );
	return;
}
void Splay( int Ind ) {
	if( Ind == 0 ) return;
	int Num = 0; Stack[ ++Num ] = Ind; int Temp = Ind;
	while( !IsRoot( Temp ) ) {
		Temp = Father[ Temp ];
		Stack[ ++Num ]  = Temp;
	}
	for( int i = Num; i >= 1; --i ) TagDown( Stack[ i ] );
	while( !IsRoot( Ind ) ) {
		int X = Father[ Ind ];
		int Y = Father[ X ];
		if( !IsRoot( X ) ) 
			if( ( Child[ Y ][ 0 ] == X ) ^ ( Child[ X ][ 0 ] == Ind ) ) 
				Rotate( Ind );
			else 
				Rotate( X );
		Rotate( Ind );
	}
	Collect( Ind );
	return;
}
void Access( int Ind ) {
	for( int i = 0; Ind; i = Ind, Ind = Father[ Ind ] ) {
		Splay( Ind ); Child[ Ind ][ 1 ] = i; Collect( Ind );
	}
	return;
}
void MakeRoot( int Ind ) {
	Access( Ind );
	Splay( Ind );
	TagOn( Ind );
	return;
}
int FindRoot( int Ind ) {
	Access( Ind ); Splay( Ind );TagDown( Ind );
	while( Child[ Ind ][ 0 ] ) {
		Ind = Child[ Ind ][ 0 ]; TagDown( Ind );
	}
	Splay( Ind );
	return Ind;
}
void Split( int x, int y ) { 
	MakeRoot( x );
	Access( y );
	Splay( y );
	return; 
}
void Link( int x, int y ) {
	MakeRoot( x );
	if( FindRoot( y ) == x ) return;
	Father[ x ] = y;
	return;
}
void Cut( int x, int y ) {
	MakeRoot( x );
	if( FindRoot( y ) != x || Child[ y ][ 0 ] || Father[ y ] != x ) return;
	Father[ y ] = Child[ x ][ 1 ] = 0;
	Collect( x );
	return;
}

int GetFather( int x ) {
	if( Fa[ x ] == x ) return x;
	Fa[ x ] = GetFather( Fa[ x ] );
	return Fa[ x ];
}

int main() {
	scanf( "%d", &Type );
	scanf( "%d%d", &N, &Q );
	for( int i = 1; i <= N; ++i ) {
		Fa[ i ] = i;
		Size[ i ] = 1;
		Rec[ i ][ 0 ] = Rec[ i ][ 1 ] = i;
	}
	int LastAns = 0;
	for( int i = 1; i <= Q; ++i ) {
		int Opt; scanf( "%d", &Opt );
		if( Opt == 1 ) {
			int u, v; scanf( "%d%d", &u, &v );
			if( Type ) u ^= LastAns, v ^= LastAns;
			int U = GetFather( u ), V = GetFather( v );
			if( U == V ) continue;

			int Max = 0, x, y;
			Split( Rec[ U ][ 0 ], Rec[ U ][ 1 ] );
			if( Size[ Rec[ U ][ 1 ] ] > Max ) {
				Max = Size[ Rec[ U ][ 1 ] ];
				x = Rec[ U ][ 0 ]; y = Rec[ U ][ 1 ];
			}
			Split( Rec[ V ][ 0 ], Rec[ V ][ 1 ] );
			if( Size[ Rec[ V ][ 1 ] ] > Max ) {
				Max = Size[ Rec[ V ][ 1 ] ];
				x = Rec[ V ][ 0 ]; y = Rec[ V ][ 1 ];
			}
			Link( u, v ); Fa[ U ] = V;
			for( int j = 0; j < 2; ++j )
				for( int k = 0; k < 2; ++k ) {
					Split( Rec[ U ][ j ], Rec[ V ][ k ] );
					if( Size[ Rec[ V ][ k ] ] > Max ) {
						Max = Size[ Rec[ V ][ k ] ];
						x = Rec[ U ][ j ]; y = Rec[ V ][ k ];
					}
				}
			Rec[ V ][ 0 ] = x; Rec[ V ][ 1 ] = y;
		} else {
			int u; scanf( "%d", &u );
			if( Type ) u ^= LastAns;
			int U = GetFather( u );
			LastAns = 0;
			for( int j = 0; j < 2; ++j ) {
				Split( Rec[ U ][ j ], u );
				LastAns = max( LastAns, Size[ u ] );
			}
			--LastAns;
			printf( "%d\n", LastAns );
			fflush( stdout );
		}
	}
	return 0;
}