Зельда хочет улучшить свойства своего Жезла Трифа и собирается использовать для этого дерево, растущее у Источника Силы. Для этого ей нужно отнести священное бревно мастеру-гному. Добравшись к дереву через весь Хайрул, она обнаружила, что это довольно большое дерево, и если она возьмет его с собой целиком, то оно превысит вместимость её рюкзака на $$$w$$$ единиц вместимости.
Где-то в своём арсенале Зельда нашла заклинание, которое на час превращает её в бобра, и теперь она собирается им наконец-то воспользоваться!
Дерево магическое (подвешенное), состоит из $$$n$$$ вершин с корнем в вершине $$$1$$$, а каждая вершина имеет свой вес $$$a_i$$$.
За одно действие Зельда-бобер может выбрать некоторую вершину дерева $$$v$$$ и откусить её со всеми её отростками (вершина $$$a$$$ является отростком вершины $$$b$$$, если кратчайший путь от вершины $$$a$$$ до корня проходит через вершину $$$b$$$).
Помогите Зельде-бобру использовать заклинание так, чтобы суммарный вес всех откушенных ею вершин был в точности равен $$$w$$$.
Первая строка входных данных содержит два целых числа $$$n$$$ и $$$w$$$ — количество вершин в дереве и необходимый вес вершин для удаления ($$$1 \le n, w \le 1000$$$).
Вторая строка входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ — веса вершин ($$$1 \le a_i \le 100$$$).
В $$$i$$$-й из следующих $$$n - 1$$$ строк даны два целых числа $$$u_i$$$ и $$$v_i$$$ — номера вершин, соединённых $$$i$$$-м ребром. Гарантируется, что данный граф является деревом ($$$1 \le u, v \le n$$$; $$$u \neq v$$$).
Если с помощью описанных действий невозможно отгрызть вершины с суммарным весом $$$w$$$, выведите $$$-1$$$.
Иначе выведите сначала целое число $$$k$$$ от $$$0$$$ до $$$n$$$ — количество превращений в бобра. Затем выведите $$$k$$$ различных целых чисел от $$$1$$$ до $$$n$$$ — номера вершин, которые нужно отгрызть.
Если существует несколько подходящих последовательностей действий, выведите любую.
5 73 4 3 2 21 22 32 44 5
2 4 3
5 83 4 3 2 21 22 32 44 5
-1
5 143 4 3 2 21 22 32 44 5
1 1
В первом примере из условия Зельда-бобер отгрызает вершины $$$3$$$ и $$$4$$$, вместе с вершиной $$$4$$$ она отгрызёт и вершину $$$5$$$, так как $$$5$$$-я вершина является отростком вершины $$$4$$$. Суммарный вес удалённых вершин $$$3$$$, $$$4$$$, $$$5$$$ равен $$$3 + 2 + 2 = 7$$$