Problem Description

In a certain country, there are $ N $ cities numbered from $ 1 $ to $ N $. There are $ M $ roads connecting these cities, where the $ i $-th road connects city $ a_i $ and city $ b_i $, built in the year $ y_i $.

The citizens of this country are very cautious, and they avoid using roads that are too old, considering them to be high-risk for accidents. Therefore, you have decided to investigate the country's traffic situation.

You are given information about $ Q $ citizens. For the $ j $-th citizen, they live in city $ v_j $ and avoid using roads built in the year $ w_j $ or earlier (including the year $ w_j $).

For each citizen, determine the number of cities that can be reached from the city they live in using only roads.

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $ a_1 $ $ b_1 $ $ y_1 $ : $ a_M $ $ b_M $ $ y_M $ $ Q $ $ v_1 $ $ w_1 $ : $ v_Q $ $ w_Q $

Output Format

Output $ Q $ lines. The $ j $-th line should contain the number of cities that the $ j $-th citizen can reach using only roads.

Sample Input and Output

Sample Input #1

5 4
1 2 2000
2 3 2004
3 4 1999
4 5 2001
3
1 2000
1 1999
3 1995

Sample Output #1

1
3
5

Sample Input #2

4 5
1 2 2005
3 1 2001
3 4 2002
1 4 2004
4 2 2003
5
1 2003
2 2003
1 2001
3 2003
4 2004

Sample Output #2

3
3
4
1
1

Sample Input #3

4 5
1 2 10
1 2 1000
2 3 10000
2 3 100000
3 1 200000
4
1 0
2 10000
3 100000
4 0

Sample Output #3

3
3
2
1

Notes/Hints

Constraints

• $1 \leq N \leq 100,000$
• $0 \leq M \leq 200,000$
• $1 \leq a_i, b_i \leq N$
• $a_i \neq b_i$
• $1 \leq y_i \leq 200,000$
• $1 \leq Q \leq 100,000$
• $1 \leq v_j \leq N$
• $0 \leq w_j \leq 200,000$

Partial Points

• For $ 50 $ points, the test cases satisfy $N \leq 1,000$, $M \leq 2,000$, $Q \leq 1,000$.

Sample Explanation 1

For each of the $ Q $ citizens, the answers are as follows:
- The first citizen lives in city $ 1 $ and does not use roads built in the year $ 2000 $ or earlier. The only road connected to city $ 1 $ was built in the year $ 2000 $, so they cannot reach any other city. Therefore, the answer is $ 1 $.
- The second citizen lives in city $ 1 $ and can reach cities $ 2 $ and $ 3 $. However, they do not use roads built before the year $ 1999 $, so they cannot reach city $ 4 $. Therefore, the answer is $ 3 $.
- The third citizen does not use roads built before the year $ 1995 $, but all roads are newer than that, so they can use all roads to reach all cities. Therefore, the answer is $ 5 $.

Sample Explanation 3

Note that there can be more than two roads between the same two cities, and there may be cities that cannot be reached even if all roads are used.

见题面 Input 部分

见题面 Output 部分