F. Suceava

Time limit: 3s Memory limit: 256MB Input: Output:

Suceava city consists of NN neighborhoods, indexed from 11 to NN, connected by N1N - 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 MM gangs, all of which are in conflict and indexed from 11 to MM. Initially, each street is occupied by a gang.

Over the course of TT 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 QQ queries (g,t)(g, t), you need to determine the insecurity level of gang gg on day tt.

Input

The first line contains two integers N,MN, M (2N105,2M105)2 \leq N \leq 10^5, 2 \leq M \leq 10^5), the number of neighborhoods and the number of gangs. The next N1N - 1 lines contain three integers u,v,gu, v, g (1uvN,1gM)1 \leq u \neq v \leq N, 1 \leq g \leq M) -the street connecting neighborhoods uu and vv, occupied by clan gg.

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

The following line contains integer QQ (1Q105)1 \leq Q \leq 10^5), the number of queries. The next QQ lines contains two integers g,tg, t (1gM,1tT)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

Log in or sign up to be able to send submissions!