描述

给定一棵 $n$个点的无根树，有 $q$次询问。

每次询问给一个参数三元组 $(a,b,c)$，求有多少个 $i$ 满足这棵树在以 $i$为根的情况下 $a$ 和 $b$ 的LCA为 $c$ 。

格式

输入格式

第一行$2$个数，为$n$ 和$q$ 。

接下来 $n-1$行，每行 $2$个数，表示树的一条边。

接下来 $q$ 行，每行 $3$ 个数，为 $(a,b,c)$。

输出格式

共 $q$行，每行一个数，为对于每个三元组的 $i$ 的个数。

样例1

输入样例1

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

输出样例1

2
1
0

样例解释

第一个查询的 $i$ 为 $3$ 和 $4$。

第二个查询的 $i$ 为 $1$。

限制

对于$100$%的数据，$1≤n≤5×10^5,1≤q≤2×10^5$。