RCPC Simulare 2023 day 2 | F. Suceava

Suceava city consists of $N$ neighborhoods, indexed from $1$ to $N$, connected by $N - 1$ bidirectional streets. It is widely recognized that you can travel between any two neighborhoods by using one or more streets.

Suceava is home to $M$ gangs, all of which are in conflict and indexed from $1$ to $M$. Initially, each street is occupied by a gang.

Over the course of $T$ days, some gang may conquer a street occupied by another gang.

We define the insecurity level of a gang as the maximum number of streets you can traverse that are occupied by the gang, while ensuring each street is traversed only once.

Being given $Q$ queries $(g, t)$, you need to determine the insecurity level of gang $g$ on day $t$.

Input

The first line contains two integers $N, M$ ($2 \leq N \leq 10^5, 2 \leq M \leq 10^5)$, the number of neighborhoods and the number of gangs. The next $N - 1$ lines contain three integers $u, v, g$ ($1 \leq u \neq v \leq N, 1 \leq g \leq M) -$the street connecting neighborhoods $u$ and $v$, occupied by clan $g$.

The following line contains integer $T$ ($1 \leq T \leq 10^5)$, the number of days. The next $T$ lines contains three integers $u, v, g$ ($1 \leq u \neq v \leq N, 1 \leq g \leq M) -$the street connecting neighborhoods $u$ and $v$ that is being conquered by gang $g$.

The following line contains integer $Q$ ($1 \leq Q \leq 10^5)$, the number of queries. The next $Q$ lines contains two integers $g, t$ ($1 \leq g \leq M, 1 \leq t \leq T) -$describing the query.

Output

For each query print the answer on a single line.

Example 1

stdin

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

stdout

2
1
2
0

Example 2

stdin

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

stdout

2
2
1
2
4
3