LCA Under Re-rooting

You are given an unrooted tree with \(n\) nodes and \(q\) queries. The tree is described by \(n-1\) undirected edges. For each query, you are given a triple \( (a,b,c) \). Your task is to count how many nodes \(i\) (with \(1 \le i \le n\)) have the property that if the tree is rooted at \(i\), then the lowest common ancestor (LCA) of nodes \(a\) and \(b\) is exactly \(c\).

The LCA of two nodes in a rooted tree is defined in the usual way. You can refer to the LCA Problem for more details.

Note: Since the tree is originally unrooted, the result may vary depending on which node is chosen as the root.

inputFormat

The first line contains two integers \(n\) and \(q\) \((1 \le n, q \le 500)\), representing the number of nodes and the number of queries respectively.

The next \(n-1\) lines each contain two integers \(u\) and \(v\), indicating an undirected edge between nodes \(u\) and \(v\).

The following \(q\) lines each contain three integers \(a\), \(b\), and \(c\), representing a query.

outputFormat

For each query, output a single integer on a new line representing the count of nodes \(i\) such that when the tree is rooted at \(i\), the LCA of nodes \(a\) and \(b\) equals \(c\).

sample

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

3
1