Iahub is very proud of his recent discovery, propagating trees. Right now, he invented a new tree, called xor-tree. After this new revolutionary discovery, he invented a game for kids which uses xor-trees.

The game is played on a tree having n nodes, numbered from 1 to n. Each node i has an initial value init_i, which is either 0 or 1. The root of the tree is node 1.

One can perform several (possibly, zero) operations on the tree during the game. The only available type of operation is to pick a node x. Right after someone has picked node x, the value of node x flips, the values of sons of x remain the same, the values of sons of sons of x flips, the values of sons of sons of sons of x remain the same and so on.

The goal of the game is to get each node i to have value goal_i, which can also be only 0 or 1. You need to reach the goal of the game by using minimum number of operations.

Input

The first line contains an integer n (1 ≤ n ≤ 10⁵). Each of the next n - 1 lines contains two integers u_i and v_i (1 ≤ u_i, v_i ≤ n; u_i ≠ v_i) meaning there is an edge between nodes u_i and v_i.

The next line contains n integer numbers, the i-th of them corresponds to init_i (init_i is either 0 or 1). The following line also contains n integer numbers, the i-th number corresponds to goal_i (goal_i is either 0 or 1).

Output

In the first line output an integer number cnt, representing the minimal number of operations you perform. Each of the next cnt lines should contain an integer x_i, representing that you pick a node x_i.

Idx	Name	Rating
A	Xor-tree	1300
B	Working out	1600
C	Guess the Tree	2300
D	Tricky Function	2200
E	Points and Segments	3000

Codeforces Round 245 (Div. 1)