题目描述
小h想要给蚯蚓安家。
蚯蚓的家园是一棵$n$个点的树。点从$1$到$n$标号。一共有$m$条蚯蚓。每条蚯蚓的家在树上的某个点上，蚯蚓的家可以重叠。
但是小h有$q$个限制。
这$q$个限制分别为第$a_i$个蚯蚓的家和第$b_i$个蚯蚓的家在树上的任何一条路径都经过了点$c_i$。
小h发现他并不会处理这些麻烦的限制，所以他向你求助。数据保证一定有解。
输入格式
从标准输入读入数据。
第一行三个正整数$n,m,q$。
接下来$n-1$行，每行两个正整数$x,y$，表示树上的一条边。
接下来$q$行，每行三个正整数$a_i,b_i,c_i$，意义如题面所示。
数据保证有解。
输出格式
输出到标准输出。
一行$m$个正整数，其中第$i$个表示第$i$个蚯蚓的家所在的地方。
样例
输入
2 2 1
1 2
1 2 1输出
1 1子任务
对于$20\%$的数据，$n,m,q\leq 5$。
对于$40\%$的数据，$n,m,q\leq 15$。
对于$100\%$的数据，$n,m\leq 250$，$q\leq 5\times 10^4$。
时间限制：$1\texttt{s}$
空间限制：$512\texttt{MB}$
