题目背景

题目来源：link。

题目描述

路路是一个喜欢强连通分量的孩子。他非常喜欢对一张图求出其强连通分量。他认为这个操作是好的。但他并不是总有能力完成这件事。现在，路路给你一张图 $G$，希望你帮他求出这张图的每个强连通分量。由于这张图的边数特别的多，他不会直接输入这张图，而是告诉你它的构造方法：

给出一棵 $n$ 个点（编号为 $1$ 到 $n$）的无根树 $T$ 和 $m$ 条指令 $(a_i,b_i,c_i)$。图 $G$ 刚开始 $n$ 个点，编号也为 $1$ 到 $n$，并且没有边。对于每一条指令 $(a_i,b_i,c_i)$，如果在树上 $b_i$ 到 $x$ 的最短路径长度（经过的边数）不超过 $c_i$，那么你会在 $G$ 中加入一条从 $a_i$ 连向 $x$ 的有向边。

请你帮帮他。

输入格式

第一行两个整数 $n$、$m$；

接下来 $n-1$ 行，每行两个整数 $a$、$b$，表示树 $T$ 中的一条边 $(a,b)$；

接下来 $m$ 行，每行三个整数 $a_i,b_i,c_i$，表示每一条指令。

输出格式

你将会需要输出 $n$ 个整数。其中第 $i$ 个整数 $p_i$ 这么输出：

• $p_1 = 1$；

• 如果点 $i$ 和点 $1$、$2$、……、$(i-1)$ 都不在同一个强连通分量中，那么 $p_i = 1 + \max\{p_1,p_2,\cdots,p_{i-1}\}$；

• 否则，假设 $i$ 和点 $j< i$ 在一个强连通分量中，并且和点 $1$、$2$、……、$(j-1)$ 都不在同一个强连通分量中，那么 $p_i = p_j$。

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

1 2 3 1 1 4 5

见附件 down\2.in

见附件 down\2.out 

提示

数据范围：

$\def\arraystretch{1.21} \begin{array}{|c|c|c|}\hline \bold{\small{子任务}}&\textbf{score}&\textbf{constraints}\\\hline \text{A}&30&c_i\le n\le 50,m\le 100\\\hline \text{B}&30&c_i\le50\\\hline \text{C}&30&\small{无特殊限制}\\\hline \end{array}$

对于所有数据，$n\le 10^5,m\le 2\times 10^5, c_i\le n$。

样例解释：

第一组指令往 $G$ 中加入了从 $5$ 连向每个点的有向边；

第二组指令往 $G$ 中加入了从 $1$ 连向 $1,2,3,4,5,6$ 的有向边；

第三组指令往 $G$ 中加入了从 $4$ 连向每个点的有向边；

最后的强连通分量为 $\{1,4,5\}$、$\{2\}$、$\{3\}$、$\{6\}$、$\{7\}$。

注：由于数据缺失，仅有 $9$ 组测试点。