题目描述

给定根为1的无权树，多次查询两个结点的最近公共祖先。

输入格式

第一行 n,q；随后 n-1 条边，再 q 行询问。

输出格式

每行输出 LCA。

样例

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

2
1
2

数据规模与约定

$1\le n,q\le200000$。