Description：

刚开始有一些点，会逐渐添加边把他们加成一棵树，随时问从某个点开始不经过重复点最远能走多远。

$1\leqslant n\leqslant 10^5$

Solution：

$link$ 的时候一定要 $makeroot$ 。

首先有一个结论就是在一棵树上从某个点开始的最长链的端点一定是直径的两个端点之一，所以我们就要求添加边，动态维护直径，还有一个结论就是合并两棵树的时候新树的直径的两个端点一定是原来两个树的直径共四个端点中取两个，于是就可以用并查集同时维护这个联通块的直径的两个端点，在合并时 $C_4^2$ 的计算一下两两之间的距离取最大值，由于强制在线所以用 $LCT$ 维护树上距离，查询的时候和直径两个端点分别求一下距离取最大即可。

如果不强制在线的话可以先把最后整个树建出来然后链剖，就不用 $LCT$ 了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<stack>

#include<cctype>

#include<cstring>

using namespace std;

#define MAXN 300010

int n,q;

struct node

{

	int fa,c[2],siz;

	bool rev;

	node(){fa = c[0] = c[1] = siz = 0;rev = false;}

}t[MAXN];

int id(int k){return (t[t[k].fa].c[0] == k ? 0 : 1);}

bool isroot(int k){return (t[t[k].fa].c[0] != k && t[t[k].fa].c[1] != k);}

void maintain(int k)

{

	t[k].siz = 1;

	if(t[k].c[0] != 0)t[k].siz += t[t[k].c[0]].siz;

	if(t[k].c[1] != 0)t[k].siz += t[t[k].c[1]].siz;

	return;

}

void connect(int k,int f,int p){t[k].fa = f;t[f].c[p] = k;return;}

void rotate(int x)

{

	int y = t[x].fa,z = t[y].fa,fx = id(x),fy = id(y);

	if(!isroot(y))t[z].c[fy] = x;

	t[x].fa = z;

	connect(t[x].c[fx ^ 1],y,fx);

	connect(y,x,fx ^ 1);

	maintain(y);maintain(x);

	return;

}

void pushdown(int k)

{

	if(t[k].rev)

	{

		t[t[k].c[0]].rev ^= 1;t[t[k].c[1]].rev ^= 1;

		swap(t[k].c[0],t[k].c[1]);t[k].rev = false;

	}

	return;

}

stack<int> s;

void splay(int x)

{

	s.push(x);

	for(int i = x;!isroot(i);i = t[i].fa)s.push(t[i].fa);

	while(!s.empty()){pushdown(s.top());s.pop();}

	while(!isroot(x))

	{

		int y = t[x].fa;

		if(isroot(y)){rotate(x);break;}

		if(id(x) == id(y)){rotate(y);rotate(x);}

		else{rotate(x);rotate(x);}

	}

	return;

}

void access(int k){for(int i = 0;k;i = k,k = t[k].fa){splay(k);t[k].c[1] = i;maintain(k);}return;}

void makeroot(int k){access(k);splay(k);t[k].rev ^= 1;return;}

void split(int x,int y){makeroot(x);access(y);splay(y);}

void link(int x,int y){makeroot(x);t[x].fa = y;return;}

void cut(int x,int y){split(x,y);t[y].c[0] = t[x].fa = 0;return;}

int query(int x,int y){split(x,y);return t[y].siz - 1;}

int f[MAXN];

int find(int x){return (x == f[x] ? x : f[x] = find(f[x]));}

int g[MAXN][2];

void merge(int a,int b)

{

	link(a,b);

	int len = -1,x,y;

	int p = find(a),q = find(b);

	if(query(g[p][0],g[p][1]) > len){len = query(g[p][0],g[p][1]);x = g[p][0];y = g[p][1];}

	if(query(g[q][0],g[q][1]) > len){len = query(g[q][0],g[q][1]);x = g[q][0];y = g[q][1];}

	if(query(g[p][0],g[q][0]) > len){len = query(g[p][0],g[q][0]);x = g[p][0];y = g[q][0];}

	if(query(g[p][0],g[q][1]) > len){len = query(g[p][0],g[q][1]);x = g[p][0];y = g[q][1];}

	if(query(g[p][1],g[q][0]) > len){len = query(g[p][1],g[q][0]);x = g[p][1];y = g[q][0];}

	if(query(g[p][1],g[q][1]) > len){len = query(g[p][1],g[q][1]);x = g[p][1];y = g[q][1];}

	f[p] = q;

	g[q][0] = x;g[q][1] = y;

	return;

}

int calc(int x)

{

	int p = find(x);

	return max(query(x,g[p][0]),query(x,g[p][1]));

}

int main()

{

	int type;

	scanf("%d",&type);

	scanf("%d%d",&n,&q);

	for(int i = 1;i <= n;++i)

	{

		f[i] = i;

		g[i][0] = g[i][1] = i;

	}

	int opt,x,y;

	int lastans = 0;

	for(int i = 1;i <= q;++i)

	{

		scanf("%d",&opt);

		if(opt == 1)

		{

			scanf("%d%d",&x,&y);

			x ^= (lastans * type);

			y ^= (lastans * type);

			merge(x,y);

		}

		else

		{

			scanf("%d",&x);

			x ^= (lastans * type);

			printf("%d\n",lastans = calc(x));

		}

	}

	return 0;

}