描述

给出一颗以1为根的N个点的树
M个询问，每次询问两个点的最近公共祖先

输入

第一行两个数N,M
接下来N-1行，每行两个数x,y表示x为y的子节点
接下来M行，每行两个数x,y

输出

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

样例

输入

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

输出

1
3
1

范围

40% N,M<=10
60% N,M<=3000
80% N,M<=\(10^6\)
100% 1<=N,M<=3*\(10^6\) 1<=x,y<=N

限制

5000ms
512M