Maximum edge cost on a tree path

You are given a tree with $N$ vertices. A tree is a connected undirected graph with no cycle. The vertices are numbered 1 to $N$, the edges are numbered 1 to $N-1$, and every edge has one cost.

Write a program that handles the following two queries.

• 1 i c: change the cost of edge $i$ to $c$.
• 2 u v: print the largest cost among the edges on the simple path from $u$ to $v$.

In a tree there is exactly one simple path between two different vertices.

The first line contains the number of vertices $N$ ($2 \le N \le 100\,000$).

Each of the next $N-1$ lines describes one edge. The $i$-th of those lines contains the two vertex numbers $u$ and $v$ joined by edge $i$ and the cost $w$ of that edge ($1 \le w \le 1\,000\,000$).

The next line contains the number of queries $M$ ($1 \le M \le 100\,000$).

Each of the next $M$ lines contains one query. A query of type 1 satisfies $1 \le i \le N-1$ and $1 \le c \le 1\,000\,000$. A query of type 2 satisfies $1 \le u, v \le N$, and $u$ differs from $v$.

For each query of type 2, print the answer on its own line, in the order the queries are given.