调了好久。。。。
•把树视为以1为根的有向树，然后将1删除
•原树变为一个森林，并且任一棵树的根节点均为原树中1的子节点
•只需要考虑最小编号前3小的三棵树
•记f[x][y]为去掉x和y两棵树后的最小值
•记dui[u]为u节点所在的树的根节点
•记dp[u]为在dui[u]这颗树中，不在路径<dui[u], u>上的节点编号最小值
•对于经过根节点的询问<u, v>
•ans<u, v> = min(dp[u], dp[v], f[bel[u]][bel[v]])
•维护g[x][0]和g[x][1]，分别表示以x的子节点为根的子树中，编号最小值和次小值
•记F[x]为删除<bel[x], x>这条路径及x的子树，编号的最小值
•dp[u] = min(F[u], g[u][0])
•时间复杂度O(N)，空间复杂度O(N)
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm>
#define re(i,l,r) for(int i=(l);i<=(r);i++)
#define rre(i,r,l) for(int i=(r);i>=(l);i--)
using namespace std;
const int xxx=;
int n,m,head[xxx],Next[xxx<<],zhi[xxx<<],fa[xxx],ed;
int g[xxx][],f[][],dui[xxx],F[xxx],dp[xxx],xiao[];
void add(int a,int b)
{
Next[++ed]=head[a],head[a]=ed,zhi[ed]=b;
Next[++ed]=head[b],head[b]=ed,zhi[ed]=a;
}
const int L=1e7;
char in[L],*In,*End;
char getc(){
if(In==End){
End=in+fread(in,,L,stdin);
if(in==End) return ;
In=in;
}
return *In++;
}
int inin(int &x){
static char c;
for(;c=getc(),!isdigit(c) && c;);
if(!c) return ;
for(x=;isdigit(c);c=getc()) (x*=)+=c-'';
return ;
}
void dfs(int x)
{
g[x][]=;g[x][]=;
for(int i=head[x];i;i=Next[i])if(zhi[i]!=fa[x])
{
fa[zhi[i]]=x;
dfs(zhi[i]);
int temp=min(g[zhi[i]][],zhi[i]);
if(temp<=g[x][])
g[x][]=g[x][],
g[x][]=temp;
else g[x][]=min(g[x][],temp);
// else g[x][1]=min(g[x][1],g[zhi[i]][0]);
}
}
void dfsxxx(int x,int t)
{
dui[x]=t;
for(int i=head[x];i;i=Next[i])if(zhi[i]!=fa[x])
dfsxxx(zhi[i],t);
}
void dfs2(int x)
{
if(x>&&fa[x]!=)
if(g[fa[x]][]==min(g[x][],x))
F[x]=min(F[fa[x]],g[fa[x]][]);
else F[x]=min(F[fa[x]],g[fa[x]][]);else ;
if(fa[x]==)F[x]=;
dp[x]=min(F[x],g[x][]);
for(int i=head[x];i;i=Next[i])if(zhi[i]!=fa[x])
dfs2(zhi[i]);
}
//void dfs3(int x)
//{
// for(int i=head[x];i;i=Next[i])if(zhi[i]!=fa[x])
// dfs3(zhi[i]);
//}
int hhh(int x)
{
x=dui[x];
if(min(x,g[x][])==xiao[])return ;
else if(min(x,g[x][])==xiao[])return ;
else if(min(x,g[x][])==xiao[])return ;
else return ;
}
int pre=;
int main()
{
freopen("in.in","r",stdin);
freopen("out.out","w",stdout);
while(inin(n))
{
inin(m);
pre=;
memset(head,,sizeof(head));ed=;
re(i,,n)
{
int a,b;
// scanf("%d%d",&a,&b);
inin(a),inin(b);
add(a,b);
}
dfs();
xiao[]=xiao[]=xiao[]=n+;
for(int i=head[];i;i=Next[i])
{
dfsxxx(zhi[i],zhi[i]);
int temp=min(g[zhi[i]][],zhi[i]);
if(xiao[]>temp)
xiao[]=xiao[],
xiao[]=xiao[],
xiao[]=temp;
else if(xiao[]>temp)
xiao[]=xiao[],
xiao[]=temp;
else if(xiao[]>temp)
xiao[]=temp;
}
f[][]=xiao[];
f[][]=f[][]=xiao[],f[][]=f[][]=xiao[],f[][]=f[][]=xiao[];
f[][]=f[][]=xiao[],f[][]=f[][]=xiao[],f[][]=f[][]=xiao[];
dfs2();
// dfs3(1);
dui[]=-;
re(i,,m)
{
int a,b;
// scanf("%d%d",&a,&b);
inin(a),inin(b);
a=a^pre,b=b^pre;
if(a==)a++;if(b==)b++;if(a>n)a=a%n+;if(b>n)b=b%n+;
// printf("%d %d %d\n",a,b,pre);
if(dui[a]==dui[b]&&dui[a]!=-){pre=;}
else if(a==)
if(b==){pre=xiao[];}
else
{
int now=hhh(b);
re(i,,)if(i!=now){pre=min(dp[b],xiao[i]);break;}
}
else if(b==)
{
int now=hhh(a);
re(i,,)if(i!=now){pre=min(dp[a],xiao[i]);break;}
}
else {pre=min(min(dp[a],dp[b]),f[hhh(a)][hhh(b)]);}
printf("%d\n",pre);
}
}
return ;
}