## DMOPC '19 Contest 7 P3 - Tree Pruning

View as PDF

Points: 12 (partial)
Time limit: 2.0s
Memory limit: 512M

Author:
Problem type

Bob's favourite tree consists of nodes connected by branches. Each node has a certain weight and the weight of a tree is the sum of the weights of its individual nodes. Bob is trying to enter his tree in a competition, but there is a weight limit of . Namely, only trees with weights that fall within the range can be entered into the competition. Bob is willing to prune some nodes off his tree such that he is left with a tree which can be entered into the competition. Note that the tree Bob enters into the competition must be connected. Help him find any such tree or determine that no such tree exists.

#### Input Specification

The first line contains two space-separated integers,  .
The second line contains space-separated integers, .
The next lines contain two space-separated integers,  , denoting a branch connecting nodes and .

#### Output Specification

If no solution exists, output -1.
Otherwise, output , the number of nodes in the tree Bob can enter into the competition, followed by the nodes of the tree on the second line. If there are multiple solutions, output any one of them.

You will receive a Presentation Error verdict if any of the following are true:

• You do not output enough.
• You output an invalid value of ( or ).
• You do not output the right number of unique nodes (i.e. not equal to ).
• You do not output a valid node (i.e. you print an index less than or greater than ).

You will receive a Wrong Answer verdict if the weight of your tree does not satisfy the constraints OR if your tree is not connected.

#### Constraints     #### Sample Input

5 9
3 6 2 3 8
1 2
2 3
3 4
4 5

#### Sample Output

3
2 3 4

#### Explanation of Sample Output

Initially, the tree has a weight of . Bob can prune off nodes and (with weights of and respectively) to obtain a final tree of weight .

Alternatively, another acceptable answer would be:

4
2 4 1 3