Description:
Doremy has a rooted tree of size $$$n$$$ whose root is vertex $$$r$$$. Initially there is a number $$$w_i$$$ written on vertex $$$i$$$. Doremy can use her power to perform this operation at most $$$k$$$ times:
1. Choose a vertex $$$x$$$ ($$$1 \leq x \leq n$$$).
2. Let $$$s = \frac{1}{|T|}\sum_{i \in T} w_i$$$ where $$$T$$$ is the set of all vertices in $$$x$$$'s subtree.
3. For all $$$i \in T$$$, assign $$$w_i := s$$$.
Doremy wants to know what is the lexicographically smallest$$$^\dagger$$$ array $$$w$$$ after performing all the operations. Can you help her?
If there are multiple answers, you may output any one.
$$$^\dagger$$$ For arrays $$$a$$$ and $$$b$$$ both of length $$$n$$$, $$$a$$$ is lexicographically smaller than $$$b$$$ if and only if there exist an index $$$i$$$ ($$$1 \leq i \le n$$$) such that $$$a_i < b_i$$$ and for all indices $$$j$$$ such that $$$j<i$$$, $$$a_j=b_j$$$ is satisfied.
Input Format:
The input consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1\le t\le 10^4$$$) — the number of test cases. The description of the test cases follows.
The first line contains three integers $$$n$$$, $$$r$$$, $$$k$$$ ($$$2 \le n \le 5000$$$, $$$1 \le r \le n$$$, $$$0 \le k \le \min(500,n)$$$).
The second line contains $$$n$$$ integers $$$w_1,w_2,\ldots,w_n$$$ ($$$1 \le w_i \le 10^6$$$).
Each of the next $$$n-1$$$ lines contains two integers $$$u_i$$$, $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$), representing an edge between $$$u_i$$$ and $$$v_i$$$.
It is guaranteed that the given edges form a tree.
It is guaranteed that the sum of $$$n$$$ does not exceed $$$50\,000$$$.
Output Format:
For each test case, In the first line, output a single integer $$$cnt$$$ ($$$0 \le cnt \le k$$$) — the number of operations you perform.
Then, in the second line output $$$cnt$$$ integers $$$p_1,p_2,\ldots,p_{cnt}$$$ — $$$x$$$ is chosen to be $$$p_i$$$ for $$$i$$$-th operation.
If there are multiple answers, you may output any one.
Note:
In the first test case:
At first $$$w=[1,9,2,6,1,8]$$$. You can choose some vertex $$$x$$$ to perform at most one operation.
- If $$$x=1$$$, $$$w=[\frac{9}{2},\frac{9}{2},\frac{9}{2},\frac{9}{2},\frac{9}{2},\frac{9}{2}]$$$.
- If $$$x=2$$$, $$$w=[1,\frac{15}{2},2,\frac{15}{2},1,8]$$$.
- If $$$x=3$$$, $$$w=[1,9,\frac{11}{3},6,\frac{11}{3},\frac{11}{3}]$$$.
- If $$$x \in \{4, 5, 6\}$$$, $$$w=[1,9,2,6,1,8]$$$.
- If you don't perform any operation, $$$w=[1,9,2,6,1,8]$$$.
$$$w$$$ is lexicographically smallest when $$$x=2$$$.