St. Petersburg is located on
islands that are connected by
bridges. Islands are labeled by integers
from
to
, and bridges — from
to
. Every bridge connects two distinct islands. Some bridges were
built in Peter the Great era, and some of them were built recently. That's why different bridges have
different weight limits. Namely, only the cars with weight not exceeding
can drive through the
-th
bridge. Sometimes some of the bridges in St. Petersburg are being renovated, but this doesn't necessarily
make the bridge stronger, so, some of
may either increase or decrease. You develop a product that will
help citizens and city guests. Currently, you develop a module that has to answer two types of queries:
- The weight limit of bridge
became equal to
.
- Count the number of islands, that can be reached by the car of weight equal to
from island
.
Answer all queries of the second type.
Input
The first line contains two integers
and
— the number of islands and bridges in St. Petersburg
.
The
-th of the following
lines contains three integers
,
, and
that describe the bridge connecting
islands
and
, initially its weight limit equals to
.
The following line contains a single integer
— the number of queries
. The following
lines contain queries.
The description of each query starts with an integer
.
If
, the query is of the first type, then two integers
and
follow, they mean that the weight limit
of the bridge
becomes equal to
.
If
, the query is of the second type, then two integers
and
follow, that describe a car of weight
located on island
.
Output
For each query of the second type print the answer on a separate line.
Scoring
Subtask 1 (points: 13)
.
Subtask 2 (points: 16)
Islands and bridges form a chain,
.
Subtask 3 (points: 17)
Islands and bridges form a complete binary tree,
.
Subtask 4 (points: 14)
All
equal to
.
Subtask 5 (points: 13)
Islands and bridges form a tree,
.
Subtask 6 (points: 27)
No additional constraint.
Sample Input 1
Copy
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
Sample Output 1
Copy
3
2
3
Sample Input 2
Copy
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
Sample Output 2
Copy
1
7
7
5
7
7
4
Explanation
Green lines represent bridges that the car from the query can drive through. Green vertices represent
islands that are reachable by this car. Arrow points to the island, where the car is located initially.
Comments