## APIO '19 P2 - Bridges

View as PDF

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

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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:

1. The weight limit of bridge became equal to .
2. 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.

Note: The official time limit is 2.0s

#### 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 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 2 (points: 16)

Islands and bridges form a chain, .

##### Subtask 3 (points: 17)

Islands and bridges form a complete binary tree, .

All equal to .

##### Subtask 5 (points: 13)

Islands and bridges form a tree, .

#### Sample Input 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

#### Sample Output 1

3
2
3

#### Sample Input 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

#### Sample Output 2

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.