Problem Background

The total length of all waterways in St. Petersburg is approximately 282 kilometers, and the water area covers 7% of the city's area. — From Wikipedia

Problem Description

St. Petersburg is located on \( n \) islands connected by \( m \) bridges. The islands are numbered from 1 to \( n \), and the bridges are numbered from 1 to \( m \). Each bridge connects two distinct islands. Some bridges were built during the time of Peter the Great, while others were built more recently. This has resulted in different bridges having different weight limits. More specifically, only vehicles weighing no more than \( d_i \) can pass over the \( i \)-th bridge. Sometimes, some bridges in St. Petersburg undergo renovation, but this does not necessarily improve the weight limit of the bridge; that is, the \( d_i \) of the renovated bridge may increase or decrease. You are preparing to develop a product to assist citizens and city visitors. Currently, the module you are developing needs to perform two types of operations:

1. Change the weight limit of bridge \( b_j \) to \( r_j \).

2. Count how many different islands a vehicle weighing \( w_j \) can reach starting from island \( s_j \).

Please answer all the answers for the second type of operation.

Input Format

The first line contains two integers \( n \) and \( m \) — the number of islands and the number of bridges in St. Petersburg, respectively.

The next \( m \) lines each contain three integers \( u_i \), \( v_i \), and \( d_i \). The \( i \)-th line describes a bridge connecting island \( u_i \) and island \( v_i \) with an initial weight limit of \( d_i \).

The next line contains a single integer \( q \) — the number of operations.

The next \( q \) lines describe the operations in order.

Each line starts with an integer \( t_j \) indicating the type of operation:

• If \( t_j = 1 \), the operation is of the first type, followed by two integers \( b_j \) and \( r_j \), indicating that the weight limit of bridge \( b_j \) will be changed to \( r_j \).

• If \( t_j = 2 \), the operation is of the second type, followed by two integers \( s_j \) and \( w_j \), indicating that a vehicle weighing \( w_j \) will start from the \( s_j \)-th island.

Output Format

For each query of the second type, output a single integer on a new line representing the answer.

Sample Input and Output

Input Sample #1

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

Output Sample #1

3
2
3

Input Sample #2

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

Output Sample #2

1
7
7
5
7
7
4

Notes/Hints

For all data, \( 1 \leq n \leq 5 \times 10^4 \), \( 0 \leq m \leq 10^5 \), \( 1 \leq q \leq 10^5 \). It is guaranteed that \( 1 \leq u_i, v_i, s_j \leq n \), \( u_i \neq v_i \), \( 1 \leq d_i, r_j, w_j \leq 10^9 \), \( 1 \leq b_j \leq m \), \( t_j \in \{1, 2\} \).

Detailed subtask additional restrictions and scores are as follows (Note: The subtasks given here are unrelated to the final evaluation of this problem and are for reference only):

见题面 Input 部分

见题面 Output 部分