408055: GYM102968 E Two Gangs

The Federal Intelligence has cracked the supply chains of two major drug cartels in the state of Middleware.

The two supply chains are represented by two trees that share the same $$$N$$$ nodes. Each node represents a city and appears in each of the supply chains exactly once.

In addition to the exact layout of the two supply chains, the intelligence also uncovered a list with the approximate number of major producers for each supply node. So, for each node in the first supply chain the Feds know $$$a_i$$$, which they assume is the number of major producers among its suppliers. Similarly, they know a list $$$b_i$$$ in connection with the second supply chain.

The State Detectives have been tasked to uncover and eliminate the major producers. However, since they are corrupt and receive regular payments from the dealers, they aren't going to make a big fuss out of it: They will instead raid a minimum amount of city hubs such that for each existing city $$$i$$$, at least $$$a_i$$$ cities in its subtree within the first supply chain, and at least $$$b_i$$$ cities in its subtree within the second supply chain will have been raided. This way, the Feds won't suspect anything.

The first line of the input contains $$$N$$$, the number of cities.

Each of the following $$$N-1$$$ lines contain two numbers $$$x$$$ and $$$y$$$, meaning that city $$$y$$$ is supplied by city $$$x$$$ in the first chain, $$$1 \leq x, y \leq N$$$.

Line $$$N+1$$$ contains $$$N$$$ numbers: $$$a_1, a_2 \dots a_N$$$.

Similarly, the next $$$N$$$ lines describe the information for the second supply chain. $$$1 \leq N \leq 100$$$ and $$$0 \leq a_i, b_i \leq$$$ their respective subtree sizes.

The first line of the output should contain one integer $$$K$$$, representing the minimum number of cities to raid such that all the thresholds in the two supply chains are met.

The second line of the output should contain $$$K$$$ integers, representing a list of raided cities such that all the thresholds in the two supply chains are met. If there are multiple solutions, print any of them.

6
3 4
2 3
3 1
6 2
4 5
0 3 0 0 0 0
5 2
2 3
3 4
5 1
5 6
1 0 0 0 3 1

4
1 3 4 6

7
3 4
3 6
4 7
3 2
6 5
6 1
0 0 3 1 0 3 0
7 5
5 1
1 2
2 6
6 3
3 4
2 2 0 0 1 0 0

4
1 4 5 6