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.

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$.

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.