描述

给定一棵 \(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\)。