You have to transport a large tree. The tree is rooted and consists of $$$n$$$ vertices with the root at vertex $$$1$$$, and each vertex has its own weight $$$a_i$$$. The weight of a tree is a total weight of its vertices.
Sadly the tree exceeds the capacity of your backpack by $$$w$$$ units of weight.
So in one action, you can choose a certain vertex $$$v$$$ and cut it off along with its subtree (all vertices $$$u$$$ such that a path between $$$u$$$ and root contains $$$v$$$). Your goal is to cut vertices with a total weight of exactly $$$w$$$.
Determine if it's possible.
The first line of input contains two integers $$$n$$$ and $$$w$$$ — the number of vertices in the tree and the required weight of the vertices to be removed ($$$1 \le n, w \le 1000$$$).
The second line of input contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ — the weights of the vertices ($$$1 \le a_i \le 100$$$).
In each of the next $$$n - 1$$$ lines, there are two integers $$$u_i$$$ and $$$v_i$$$ — the numbers of the vertices connected by the $$$i$$$-th edge. It is guaranteed that the given graph is a tree ($$$1 \le u, v \le n$$$; $$$u \neq v$$$).
If it is impossible to cut off vertices with a total weight of $$$w$$$ using the described actions, output $$$-1$$$.
Otherwise, first output an integer $$$k$$$ from $$$0$$$ to $$$n$$$ — the number of cuts. Then output $$$k$$$ distinct integers from $$$1$$$ to $$$n$$$ — the numbers of the vertices that need to be cut off. No two printed vertices should be a child and an ancestor.
If there are multiple suitable sequences of actions, output any.
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
In the first example, you can cut off vertices $$$3$$$ and $$$4$$$, and along with vertex $$$4$$$, you will also cut off vertex $$$5$$$, since vertex $$$5$$$ is in a subtree of vertex $$$4$$$. The total weight of the removed vertices $$$3$$$, $$$4$$$, $$$5$$$ equals $$$3 + 2 + 2 = 7$$$.
