#include #include #include #include using namespace std; vectorv[300005]; int Tree[300005],st[300005],ed[300005],i,j,m,n,p,k,tot,x,y,deep[300005],fa[200005][20],a[300005],q,ans; void get(int x) { int i; for (i=1;i<=18;++i) fa[x][i]=fa[fa[x][i-1]][i-1]; } void dfs(int x) { get(x); int i; st[x]=++tot; for (i=0;i=0;--i) if (k&(1<=0;--i) if (fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i]; return fa[x][0]; } int main() { int T; scanf("%d",&T); for (;T--;) { for (i=1;i<=2*n;++i) Tree[i]=deep[i]=0; tot=0; for (i=1;i<=n;++i) for (j=0;j<=18;++j) fa[i][j]=0; scanf("%d%d",&n,&q); for (i=1;i