Description

Saint Petersburg is located on $n$ islands connected by $m$ bridges. The islands are numbered with integers from $1$ to $n$, and the bridges are numbered with integers from $1$ to $m$. Each bridge connects two different islands. Some bridges were built in the era of Peter the Great, while others were built more recently. As a result, different bridges may have different weight limits. More specifically, only cars with weight not exceeding $d_i$ can cross bridge $i$. Sometimes, some bridges in Saint Petersburg are renovated, but this does not necessarily make their load capacity better; that is, after renovation, the $d_i$ of a bridge may increase or decrease. You are going to develop a product to help citizens and city visitors. Currently, the module you are developing needs to support two types of operations:

1. Change the weight limit of bridge $b_j$ to $r_j$.

2. Count how many different islands a car of weight $w_j$ can reach starting from island $s_j$.

Please answer all queries of the second type.

Input Format

The first line contains two integers $n$ and $m$, representing the number of islands and the number of bridges in Saint Petersburg.

The next $m$ lines each contain three integers $u_i, v_i, d_i$. Line $i$ describes a bridge connecting islands $u_i$ and $v_i$, with an initial weight limit of $d_i$.

The next line contains one integer $q$, representing the number of operations.

The next $q$ lines describe the operations in order, one per line.

The first integer on each line is $t_j$, indicating the operation type:

• If $t_j = 1$, this is the first type of operation. The line then contains two integers $b_j$ and $r_j$, meaning the weight limit of bridge $b_j$ will become $r_j$.

• If $t_j = 2$, this is the second type of operation. The line then contains two integers $s_j$ and $w_j$, meaning a car of weight $w_j$ will start from island $s_j$.

Output Format

For each query of the second type, output one line with one integer representing the answer.

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

3
2
3

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

1
7
7
5
7
7
4

Hint

For all testdata, $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$, and $t_j \in \{1, 2\}$.

The detailed additional constraints and scores for the subtasks are shown in the table below.

Translated by ChatGPT 5