Doremy 有一棵大小为 $n$ 的有根树，其根节点为 $r$。起初，每个节点 $i$ 上都写有一个数字 $w_i$。Doremy 可以使用她的能力，进行至多 $k$ 次以下操作：

1. 选择一个节点 $x$ ($1 \le x \le n$)。
2. 令 $s = \frac{1}{|T|} \sum_{i \in T} w_i$，其中 $T$ 是 $x$ 的子树中所有节点的集合。
3. 对于所有 $i \in T$，赋值 $w_i := s$。

Doremy 想知道在执行完所有操作后，字典序最小的数组 $w$ 是什么。你能帮帮她吗？

如果有多个答案，你可以输出其中任意一个。

对于两个长度均为 $n$ 的数组 $a$ 和 $b$，$a$ 的字典序小于 $b$ 当且仅当存在一个下标 $i$ ($1 \le i \le n$)，使得 $a_i < b_i$，且对于所有满足 $j < i$ 的下标 $j$，均满足 $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, \dots, w_n$ ($1 \le w_i \le 10^6$)。

接下来的 $n - 1$ 行，每行包含两个整数 $u_i, v_i$ ($1 \le u_i, v_i \le n$)，表示 $u_i$ 和 $v_i$ 之间的一条边。

保证给定的边构成一棵树。

保证所有测试用例中 $n$ 的总和不超过 $50\,000$。

输出格式

对于每个测试用例，第一行输出一个整数 $cnt$ ($0 \le cnt \le k$) — 你执行的操作次数。

接下来，在第二行输出 $cnt$ 个整数 $p_1, p_2, \dots, p_{cnt}$ — 其中 $p_i$ 表示第 $i$ 次操作中选择的节点 $x$。

如果有多个答案，你可以输出其中任意一个。

样例

输入样例 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$ 的字典序最小。