思路:考试的时候打了LCT，自以为能过，没想到只能过80..
考完一想:lct的做法点数是100W,就算是nlogn也会T。
讲一下lct的做法把:首先如果一条边连接的两个点都在同一个联通块内，那么这条边对答案没有影响，可以忽略，因此，问题变成了每次询问两个点中路径上权值最大的边(这里的权值我们令它为加入这条边的时间)，边我们用一个点连接两个端点来表示。
正解:由于是无根树，因此我们用并查集按秩合并，每次把小的加到大的里面去，询问的时候暴力走lct查找最大即可。
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
int fa[],n,m,size[],ty[],vis[],vistag;
int read(){
int t=,f=;char ch=getchar();
while (ch<''||ch>''){if (ch=='-')f=-;ch=getchar();}
while (''<=ch&&ch<=''){t=t*+ch-'';ch=getchar();}
return t*f;
}
int find(int x){
if (fa[x]==x) return x;
else return fa[x]=find(fa[x]);
}
int main(){
n=read();m=read();
for (int i=;i<=n;i++) fa[i]=size[i]=,ty[i]=;
int Case=,lastans=;
for (int i=;i<=m;i++){
int opt=read(),u=read()^lastans,v=read()^lastans;
if (!opt){
++Case;
u=find(u),v=find(v);
if (u!=v){
if (size[u]>size[v]) std::swap(u,v);
fa[u]=v;
size[v]+=size[u];
ty[u]=Case;
}else{
++vistag;
int fu=u,fv=v;
for (;;u=fa[u]){
vis[u]=vistag;
if (fa[u]==u) break;
}
int lca=;
for (;;v=fa[v]){
if (vis[v]==vistag&&!lca) lca=v;
if (fa[v]==v) break;
}
if (u!=v){
printf("%d\n",lastans=);
continue;
}else{
int ans=;
for (;fu!=lca;fu=fa[fu]) ans=std::max(ans,ty[fu]);
for (;fv!=lca;fv=fa[fv]) ans=std::max(ans,ty[fv]);
printf("%d\n",lastans=ans);
}
}
}
}
}