查询最近公共祖先

难度：T4

【知识点：倍增LCA】

前置知识：倍增LCA及其冻结前置单元。

题目描述与输入

第一行$n$ $m$，随后$m$行树边$u$ $v$ $w$（忽略$w$）；再读$q$，随后$q$行$u$ $v$。查询根为$1$时$u$与$v$的最近公共祖先编号。

规则说明

一个点的祖先包括它自己，以及沿父节点一直走到根所经过的点。两个点的最近公共祖先，是它们共同祖先中离根最远的那个；查询两点相同时，结果就是该点。

输出

每个查询输出一行结果。

数据范围

$1 \le n \le 80$，$m=n - 1$，$1 \le q \le 200$；$w$为占位值，根为$1$。

样例输入

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

样例输出

2
2
1
4

样例说明

四次最近公共祖先分别为$2$、$2$、$1$、$4$。