【问题描述】

​ 圣诞节马上要到了，小 $\text{X}$ 买一棵有 $n$ 个结点的圣诞树，从 $1$ 到 $n$ 编号，他打算自己动手装扮一下圣诞树，给圣诞树挂上 $m$ 个礼物，每个礼物都挂在树上的某个结点上，礼物可以重叠。

​ 为了使圣诞树看起来很漂亮，小 $\text{X}$ 认为必须满足给定的 $Q$ 个限制条件，限制条件中第 $i$ 个形如 $\text{“}$ 第 $a_i$ 个礼物和第 $b_i$ 个礼物在树上的最短路径经过了点 $c_i$ $\text{”}$。

​ 小 $\text{X}$ 想要构造出满足 $Q$ 个限制条件挂礼物的圣诞树方案。

【输入格式】

​ 从文件 $tree.in$ 中读入数据。

​ 第一行三个正整数 $n, m, Q$ 。

​ 接下来 $n-1$ 行，每行两个正整数 $x_i, y_i$，表示树上的一条边。

​ 接下来 $Q$ 行，每行三个正整数 $a_i, b_i, c_i$，意义如题面所示。

​ 数据保证有解。

【输出格式】

​ 输出到文件 $tree.out$ 中。

​ 输出一行 $m$ 个正整数，其中第 $i$ 个表示第 $i$ 个礼物所在的结点编号。

【样例输入1】

2 2 1 
1 2 
1 2 1

【样例输出1】

1 1

【样例2】

​ 见选手目录下的 $ex\_tree2.in$ 与 $ex\_tree2.ans$。

【数据范围及约定】