Problem Description

Given an undirected tree with $n$ nodes and $q$ queries.

Each query provides a triplet of parameters $(a, b, c)$, and you need to find how many nodes $i$ satisfy that the LCA of $a$ and $b$ is $c$ when the tree is rooted at $i$.

Input Format

The first line contains two numbers, $n$ and $q$.

The next $n-1$ lines each contain two numbers, representing an edge of the tree.

The next $q$ lines each contain three numbers, representing the triplet $(a, b, c)$.

Output Format

Output $q$ lines, each containing a single number, which is the count of $i$ for each triplet.

Sample Input and Output

Input Sample #1

10 5
1 2
1 3
2 4
2 5
2 10
5 6
3 7
7 8
7 9
4 6 2
4 10 1
6 8 3
9 10 2
4 10 5

Output Sample #1

7
0
1
4
0

Input Sample #2

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

Output Sample #2

2
1
0

Input Sample #3

20 10
1 2
1 3
1 4
2 5
2 6
3 10
4 13
4 14
6 7
6 8
10 11
4 15
4 16
8 9
11 12
16 17
16 18
16 19
17 20
15 19 16
1 12 1
20 20 20
7 7 8
1 8 3
5 20 2
2 9 6
9 12 1
9 12 2
9 12 3

Output Sample #3

4
16
20
0
0
5
2
10
2
1

Notes

Sample 2 Explanation

For the first query, $i$ is 3 and 4.

For the second query, $i$ is 1.

Data Range

This problem is tested by subtasks:

$subtask1 (20pts)$: $1 \leq n \leq 1000$, $1 \leq q \leq 500$.

$subtask2 (15pts)$: $1 \leq n \leq 10^5$, $1 \leq q \leq 10^5$, the tree degenerates into a chain.

$subtask3 (25pts)$: $1 \leq n \leq 5 \times 10^5$, $1 \leq q \leq 10^5$, the data is not random.

$subtask4 (40pts)$: $1 \leq n \leq 5 \times 10^5$, $1 \leq q \leq 2 \times 10^5$.

For all data: $1 \leq n \leq 5 \times 10^5$, $1 \leq q \leq 2 \times 10^5$.

Note: The data intensity is not high, so there is no need to optimize for constant factors or use fast input/output.

见题面 Input 部分

见题面 Output 部分