F. Усреднённое дерево Дореми
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

У Дореми есть корневое дерево размера $$$n$$$, корнем которого является вершина $$$r$$$. Изначально на вершине $$$i$$$ записано число $$$w_i$$$. Дореми может использовать свою силу, чтобы выполнить данную операцию не более $$$k$$$ раз:

  1. Выберем вершину $$$x$$$ ($$$1 \leq x \leq n$$$).
  2. Пусть $$$s = \frac{1}{|T|}\sum_{i \in T} w_i$$$, где $$$T$$$ — множество всех вершин в поддереве $$$x$$$.
  3. Для всех $$$i \in T$$$ присваиваем $$$w_i := s$$$.

Дореми хочет узнать, каким будет лексикографически минимальный$$$^\dagger$$$ массив $$$w$$$ после выполнения всех операций. Можете ли вы ей помочь?

Если ответов несколько, вы можете вывести любой из них.

$$$^\dagger$$$ Для массивов $$$a$$$ и $$$b$$$ длины $$$n$$$, $$$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$$$-й операции.

Если ответов несколько, то можно вывести любой из них.

Пример
Входные данные
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
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]$$$.

$$$w$$$ является лексикографически наименьшим, если $$$x=2$$$.