Dynamic Grape Vine Operations

Syrup owns a huge grapevine with $N$ leaves numbered from $1$ to $N$. The leaves are connected by $N-1$ branches where the $i$th branch connects leaf $A_i$ and leaf $B_i$ with length $W_i$. Thus the leaves and branches form a tree.

Initially, there are no grapes on any leaf. Syrup can perform $Q$ operations of the following three types:

1. Water Operation: Given a leaf $j$, water it. If there is no grape on leaf $j$, a grape immediately grows; if there is already a grape present, the grape is removed.
2. Update Operation: Given a branch index $k$ (corresponding to the $k$th branch in the input), change its length to a new value $w$.
3. Query Operation: When Syrup stands on a leaf $j$, he wants to quickly find the minimum distance from $j$ to any leaf that currently has a grape. The distance between two leaves is defined as the sum of the lengths of the branches along the unique path connecting them. If no grape exists on any leaf, output $-1$.

You are given the tree configuration and the $Q$ operations. Process the operations in order and output the answer for each query operation.

inputFormat

The first line contains two integers $N$ and $Q$.

The next $N-1$ lines each contain three integers $A_i$, $B_i$, and $W_i$, describing a branch connecting leaves $A_i$ and $B_i$ with length $W_i$.

Each of the following $Q$ lines represents an operation in one of the following formats:

• For a water operation: `1 j` (toggle the grape on leaf $j$).
• For an update operation: `2 k w` (update the $k$th branch’s length to $w$; the $k$th branch is the one given in the input order).
• For a query operation: `3 j` (query from leaf $j$ to find the nearest grape).

Note that the tree is undirected and the input guarantees connectivity.

outputFormat

For each query operation (operation of type 3), output a single line containing an integer which is the minimum distance from the given leaf to any leaf that currently has a grape. If no grape exists, output -1.

sample

4 6
1 2 3
2 3 4
3 4 5
3 1
1 3
3 1
2 2 1
3 3
3 4

-1
7
0
5

</p>