Doremy 有一个大小为 $$$n$$$ 的有根树,其根是顶点 $$$r$$$。最初,顶点 $$$i$$$ 上写有一个数字 $$$w_i$$$。 Doremy 最多可以使用她的力量执行此操作 $$$k$$$ 次:
1. 选择一个顶点 $$$x$$$ ($$$1 \leq x \leq n$$$)。
2. 令 $$$s = \frac{1}{|T|}\sum_{i \in T} w_i$$$ 其中 $$$T$$$ 是 $$$x$$$ 子树中所有顶点的集合。
3. 对于 T$$$ 中的所有 $$$i,分配 $$$w_i := s$$$。
Doremy 想知道执行完所有操作后按字典顺序最小的 $$$^\dagger$$$ 数组 $$$w$$$ 是什么。你能帮助她吗?
如果有多个答案,则可以输出任意一个。
$$$^\dagger$$$ 对于长度为 $$$n$$$ 的数组 $$$a$$$ 和 $$$b$$$,$$$a$$$ 按字典顺序小于 $$$b$$$ 当且仅当存在索引 $$$i$$$ ($$$1 \leq i \le n$$$) 使得 $$$a_i < b_i$$$ 并且对于所有索引$$$j$$$ 使得$$$j<i$$$,满足$$$a_j=b_j$$$。
输入
输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1\le t\le 10^4$$$) — 测试用例的数量。测试用例的描述如下。
第一行包含三个整数 $$$n$$$、$$$r$$$、$$$k$$$ ($$$2 \le n \le 5000$$$、$$$1 \le r \le n$$$、$$$0 \le k \le \min(500,n)$$$)。
第二行包含 $$$n$$$ 整数 $$$w_1,w_2,\ldots,w_n$$$ ($$$1 \le w_i \le 10^6$$$)。
接下来的 $$$n-1$$$ 行包含两个整数 $$$u_i$$$、$$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$),表示 $$$u_i$$$ 和 $$$v_i$$$ 之间的一条边。
保证给定的边形成一棵树。
保证$$$n$$$的总和不超过$$$50\,000$$$。
输出
对于每个测试用例,在第一行中,输出一个整数 $$$cnt$$$ ($$$0 \le cnt \le k$$$) — 您执行的操作数。
然后,在第二行输出 $$$cnt$$$ 整数 $$$p_1,p_2,\ldots,p_{cnt}$$$ — $$$x$$$ 被选择为 $$$p_i$$$ 进行第 $$$i$$$ 操作。
如果有多个答案,则可以输出任意一个。
示例
输入 #1
4 6 1 1 1 9 2 6 1 8 1 2 1 3 2 4 3 6 3 5 7 7 2 3 1 3 3 1 1 2 7 1 7 2 7 4 1 5 2 3 4 6 6 5 1 3 1 3 1 1 3 5 3 5 1 5 6 3 4 1 2 3 2 1 1000000 999999 999997 2 1 1 3
输出 #1
1 2 2 1 4 1 5 1 1
注意
在第一个测试用例中:
首先$$$w=[1,9,2,6,1,8]$$$。您可以选择某个顶点 $$$x$$$ 来执行最多一项操作。
- 如果 $$$x=1$$$,$$$w=[\frac{9}{2},\frac{9}{2},\frac{9}{2},\frac{9}{2},\frac{9}{2},\frac{9}{2}]$$$。
- 如果 $$$x=2$$$,$$$w=[1,\frac{15}{2},2,\frac{15}{2},1,8]$$$。
- 如果 $$$x=3$$$, $$$w=[1,9,\frac{11}{3},6,\frac{11}{3},\frac{11}{3}]$$$。
- 如果 $$$x \in \{4, 5, 6\}$$$,$$$w=[1,9,2,6,1,8]$$$。
- 如果不执行任何操作,$$$w=[1,9,2,6,1,8]$$$。
当 $$$x=2$$$ 时,$$$w$$$ 按字典顺序最小。