Tarjan_LCA(root);
}
int main()
{
//freopen("C:\\Users\\Administrator\\Desktop\\kd.txt","r",stdin);
int tcase;
scanf("%d",&tcase);
while(tcase--)
{
scanf("%d%d",&n,&m);
Solve();
for (int i=0; i
int ans=0;
ans=d[q[i].u]-d[q[i].lca];
if(q[i].lca!=q[i].v)
ans++;
if(q[i].u==q[i].v)
ans=0;
printf("%d\n",ans);
}
}
return 0;
}