The Little Bird

You stumble upon a little bird chirping in an apple tree— what blind luck for a bird enthusiast like you! You watch it helplessly flutter its little wings, unable to take to the air. Intrigued by this minuscule marvel, you spend the next $D$ days observing it.

The apple tree has $N$ flowers, connected by $N-1$ branches. Each branch $i$ connects flowers $A_i$ and $B_i$, and has a length of $C_i$.

When you first found the little bird, it was at flower $1$. At the start of day $j$, you make an observation denoted by $T_j$ and $F_j$.

• If $T_j = 1$, an apple has grown on flower $F_j$.
• If $T_j = 2$, all apples on flower $F_j$ have fallen from the tree (and thus become completely unreachable).
• If $T_j = 3$, the little bird has climbed to flower $F_j$.

After each day, you wonder: how far from the little bird is the closest apple? If there is no apple on the tree, output $-1$ instead.

It’s time to write a program since you can’t figure it out in your head.

Input

• The first line of input contains two space-separated integers: $N$ and $D$.
• The next $N-1$ lines of input each contain three space-separated integers: $A_i$, $B_i$ and $C_i$.
• The next $D$ lines of input each contain two space-separated integers: $T_j$ and $F_j$.

Output

You should output $D$ lines. The $j$th line should contain a single integer: the distance from the little bird to the closest apple on day $j$, or $-1$ if there is no apple.

Constraints

• $1 \le N \le 10^5$
• $1 \le D \le 10^5$
• $1 \le A_i, B_i \le N$ (for all $1 \le i \le N$)
• $1 \le C_i \le 10^6$ (for all $1 \le i \le N$)
• $1 \le T_j \le 3$ (for all $1 \le j \le D$)
• $1 \le F_j \le N$ (for all $1 \le j \le D$)
• Every flower is connected to every other flower through exactly one distinct path of branches.

Subtasks

• Subtask 1 (10%): $1 \le N \le10^3$ and $1 \le D \le 10^3$.
• Subtask 2 (25%): $A_i + 1 = B_i$ (for all $1 \le i \le N$). That is, the apple tree forms a line.
• Subtask 3 (40%): $T_j \ne 2$ (for all $1 \le j \le D$). That is, no apples will be eaten.
• Subtask 4 (25%): No additional constraints.