UOJ Logo

NOI.AC

1S 512MB

#24. B

统计

题目描述

小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}$

下载

样例数据下载