APIO '19 P2 - Bridges

View as PDF

Submit solution

Points: 30 (partial)
Time limit: 1.4s
Memory limit: 512M

Problem type

St. Petersburg is located on n islands that are connected by m bridges. Islands are labeled by integers from 1 to n, and bridges — from 1 to m. 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 di can drive through the i-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 di 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:

  1. The weight limit of bridge bj became equal to rj.
  2. Count the number of islands, that can be reached by the car of weight equal to wj from island sj.

Answer all queries of the second type.

Input

The first line contains two integers n and m — the number of islands and bridges in St. Petersburg (1n50000,0m100000).

The i-th of the following m lines contains three integers ui, vi, and di that describe the bridge connecting islands ui and vi, initially its weight limit equals to di (1ui,vin;uivi;1di109).

The following line contains a single integer q — the number of queries (1q100000). The following q lines contain queries.

The description of each query starts with an integer tj (tj{1,2}).

If tj=1, the query is of the first type, then two integers bj and rj follow, they mean that the weight limit of the bridge bj becomes equal to rj (1bjm,1rj109).

If tj=2, the query is of the second type, then two integers sj and wj follow, that describe a car of weight wj located on island sj (1sjn,1wj109).

Output

For each query of the second type print the answer on a separate line.

Scoring

Subtask 1 (points: 13)

n1000,m1000,q10000.

Subtask 2 (points: 16)

Islands and bridges form a chain, m=n1,ui=i,vi=i+1 (1im).

Subtask 3 (points: 17)

Islands and bridges form a complete binary tree, n=2k1,m=n1,ui=i+12,vi=i+1 (1k15,1im).

Subtask 4 (points: 14)

All tj equal to 2.

Subtask 5 (points: 13)

Islands and bridges form a tree, m=n1.

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

There are no comments at the moment.