← 返回题目列表

Codeforces · 587/C

C. 达夫在军队

中文机器翻译题面 查看原题

最近达夫已经入伍当兵了。马雷克是她的指挥官。

他们的国家安达兹古有n个城市(编号从1到n)和n-1条双向道路。每条道路连接两个不同的城市。任意两个城市之间都存在唯一的路径。

安达兹古区还有m人居住(编号从1到m)。每个人都有一个身份证号码。第i个人的身份证号码是i,他/她住在城市ci。请注意,一座城市中可能有多个人,也可能没有人居住在城市中。

马利克喜欢点菜。这就是为什么他要求达夫回答 q 个问题。在每次查询中,他都会给出数字 v、u 和 a。

回答查询:

假设有 x 人居住在从城市 v 到城市 u 的路径上的城市中。假设这些人的 ID 依次为 p1, p2, ..., px。

如果 k = min(x, a),那么 Duff 应该按顺序告诉 Malek 数字 k、p1、p2、...、pk。换句话说,马利克想知道这条道路上的最低限度(或者更少,如果人数少于一个人)。

Duff 现在很忙,所以她请你帮助她并回答问题。

输入

输入的第一行包含三个整数,n、m 和 q (1 ≤ n、m、q ≤ 105)。

接下来的 n - 1 行包含道路。每条线包含两个整数 v 和 u,即道路的端点(1 ≤ v,u ≤ n,v ≠ u)。

下一行包含 m 个整数 c1, c2, ..., cm,用空格分隔(对于每个 1 ≤ i ≤ m,1 ≤ ci ≤ n)。

接下来的 q 行包含查询。它们每个都包含三个整数 v、u 和 a(1 ≤ v、u ≤ n 和 1 ≤ a ≤ 10)。

输出

对于每个查询,在一行中打印数字 k、p1、p2、...、pk,并用空格分隔。

示例

输入 #1

5 4 5
1 3
1 2
1 4
4 5
2 1 4 3
4 5 6
1 5 2
5 5 10
2 3 3
5 3 1

输出 #1

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

注意

示例案例中Andarz Gu的图表如下(旁边写着每个城市的人的ID):