Noah owns an unrooted tree with n vertices which are numbered from 1 to n. Every morning Noah would like to pick two vertices u and v to get influence from daylight and then the influence spreads through edges, but the influence will be disappeared if it has passed through more than w edges.
Your task is to calculate the number of vertices influenced by the daylight for each day. In addition, input data will be encrypted to make sure your solution is online.
The first line contains one integer T, indicating the number of test cases.
The following lines describe all the test cases. For each test case:
The first line contains two integers n and m.
Each of the following (n - 1) lines contains two integers u and v, indicating an edge between vertex u and vertex v.
Let be the last answer before each day. At the beginning day of each test case, is initialized as 0.
Each of the following m lines contains three integers u', v' and w', satifying , , , which means one day Noah will pick vertices u and v to get influence and the influence will be disappeared if it has passed through more than w edges.
1 ≤ T ≤ 100, 1 ≤ n, m ≤ 105, 1 ≤ u, v, u', v' ≤ n, 0 ≤ w' < n.
It is guaranteed that no more than 10 test cases do not satisfy n, m ≤ 103 and the size of the standard input file does not exceed 32 MiB.
For each day, print the answer in one line.
It is guaranteed that the size of the standard output file does not exceed 7 MiB.
The decrypted information is the following:
## Input
The first line contains one integer T, indicating the number of test cases.The following lines describe all the test cases. For each test case:The first line contains two integers n and m.Each of the following (n - 1) lines contains two integers u and v, indicating an edge between vertex u and vertex v.Let be the last answer before each day. At the beginning day of each test case, is initialized as 0.Each of the following m lines contains three integers u', v' and w', satifying , , , which means one day Noah will pick vertices u and v to get influence and the influence will be disappeared if it has passed through more than w edges.1 ≤ T ≤ 100, 1 ≤ n, m ≤ 105, 1 ≤ u, v, u', v' ≤ n, 0 ≤ w' < n.It is guaranteed that no more than 10 test cases do not satisfy n, m ≤ 103 and the size of the standard input file does not exceed 32 MiB.
## Output
For each day, print the answer in one line.It is guaranteed that the size of the standard output file does not exceed 7 MiB.
[samples]
## Note
The decrypted information is the following: Day 1: u = 1, v = 2, w = 0; Day 2: u = 1, v = 2, w = 1; Day 3: u = 1, v = 2, w = 2; Day 4: u = 1, v = 2, w = 3; Day 5: u = 1, v = 2, w = 4.
**Definitions**
Let $ T \in \mathbb{Z} $ be the number of test cases.
For each test case:
- Let $ n, m \in \mathbb{Z} $ denote the number of vertices and days, respectively.
- Let $ G = (V, E) $ be an unrooted tree with $ V = \{1, 2, \dots, n\} $ and $ |E| = n-1 $.
- Let $ d(u,v) $ denote the shortest path distance (number of edges) between vertices $ u $ and $ v $ in $ G $.
- Let $ \text{last} \in \mathbb{Z} $ be a state variable, initialized to 0 at the start of each test case.
**Constraints**
1. $ 1 \leq T \leq 100 $
2. $ 1 \leq n, m \leq 10^5 $
3. $ 0 \leq w' < n $
4. For each day, encrypted inputs $ u', v', w' $ satisfy:
$$
u = u' \oplus \text{last}, \quad v = v' \oplus \text{last}, \quad w = w' \oplus \text{last}
$$
where $ \oplus $ denotes bitwise XOR, and $ u, v \in V $, $ w \in \mathbb{Z}_{\geq 0} $.
**Objective**
For each of the $ m $ days:
- Decrypt $ u, v, w $ using $ \text{last} $.
- Compute the set of influenced vertices:
$$
S = \{ x \in V \mid d(u,x) \leq w \text{ or } d(v,x) \leq w \}
$$
- Output $ |S| $, and set $ \text{last} = |S| $ for the next day.