描述

给出一颗N个点的树
M个询问，每次询问以某点r为根，另两个点x,y的最近公共祖先

输入

第一行两个数N,M
接下来N-1行，每行两个数x,y表示x与y之间有一条边
接下来M行，每行三个数r,x,y

输出

M行，为各个询问中两个点的最近公共祖先

样例

输入

4 3
2 1
3 1
4 3
3 2 4
2 1 2
4 2 3

输出

3
2
3

范围

50% N,M<=10
70% N,M<=3000
100% 1<=N,M<=3*\(10^5\) 1<=r,x,y<=N

限制

2000ms
256M