Turing Daughter

题目描述

Turing Daughter is Turing Grandma's granddaughter. Like her grandmother, she also loves knitting wool sweaters.

Each sweater she knits is represented by an unweighted tree with $n$ vertices numbered $1,2,\ldots,n$. Its $n-1$ edges have pairwise distinct colors numbered $1,2,\ldots,n-1$.

She first knits a sweater $T_0$. She then modifies it $n-1$ times in order, producing the sweaters $T_1,T_2,\ldots,T_{n-1}.$

In the $i$-th modification, she removes the edge of color $e_i$ from $T_{i-1}$ and knits that edge back between vertices $u_i$ and $v_i$, keeping its color $e_i$. It is guaranteed that the resulting sweater is still represented by a tree.

Therefore, there are exactly $n$ sweaters: $T_0,T_1,\ldots,T_{n-1}$.

The complexity of a sweater is the diameter of its tree: the greatest number of edges on a simple path between two of its vertices. In particular, a sweater consisting of a single vertex has complexity $0$.

For a sweater $T$, removing its edge of color $x$ splits it into two smaller sweaters, whose trees are the two connected components $C_1$ and $C_2$. Define $f(T,x)=\max\bigl(\operatorname{diameter}(C_1),\operatorname{diameter}(C_2)\bigr).$

There are $q$ queries. In each query, Turing Daughter chooses a time interval $[l,r]$ and removes the edge of color $x$ from every sweater $T_l,T_{l+1},\ldots,T_r$. This leaves exactly $2(r-l+1)$ smaller sweaters. She wants to know the maximum complexity among all of them, that is, $\max_{i=l}^{r} f(T_i,x).$

输入格式

The first line contains two integers $n$ and $q$ ($2\le n\le 5\times 10^4$, $1\le q\le 5\times 10^4$).

The next $n-1$ lines describe $T_0$. The $e$-th of these lines contains two integers $u_e$ and $v_e$ ($1\le u_e,v_e\le n$), indicating that the edge of color $e$ connects vertices $u_e$ and $v_e$.

The next $n-1$ lines describe the modifications. The $i$-th of these lines contains three integers $e_i,u_i,v_i$ ($1\le e_i \lt n$, $1\le u_i,v_i\le n$), describing the modification that transforms $T_{i-1}$ into $T_i$.

The next $q$ lines each contain three integers $l,r,x$ ($0\le l\le r \lt n$, $1\le x \lt n$), describing a query.

It is guaranteed that $T_0$ and the graph obtained after every modification are trees.

输出格式

For each query, output one integer on a separate line.

样例输入 #1

4 4
1 2
2 3
3 4
1 1 2
2 1 3
3 2 4
0 0 2
0 3 2
1 2 1
2 3 3

样例输出 #1

1
2
2
2