树上边数距离

难度：T4

【知识点：倍增LCA】

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

题目描述与输入

第一行$n$ $m$，随后$m$行树边$u$ $v$ $w$（忽略$w$）；再读$q$，随后$q$行$u$ $v$。查询$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

样例输出

3
0
3
1

样例说明

四条简单路径边数分别为$3$、$0$、$3$、$1$，边权不参与本题。