Problem: 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 initi, 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 goali, 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 ≤ 105). Each of the next n - 1 lines contains two integers ui and vi (1 ≤ ui, vi ≤ n; ui ≠ vi) meaning there is an edge between nodes ui and vi. 

The next line contains n integer numbers, the i-th of them corresponds to initi (initi is either 0 or 1). The following line also contains n integer numbers, the i-th number corresponds to goali (goali 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 xi, representing that you pick a node xi.

Examples

Input

10
2 1
3 1
4 2
5 1
6 2
7 5
8 6
9 8
10 5
1 0 1 1 0 1 0 1 0 1
1 0 1 0 0 1 1 1 0 1


Output

2
4
7

Solution (in JAVA):

Solution:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
import java.util.StringTokenizer;

/**
 *
 * @author Juan David Barreto
 */
public class Xor_Tree_Stack {

    // An array of lists which represents the tree
    static List<Integer>[] tree;
    // A list containing the nodes who need to be flipped
    static List<Integer> answer;
    // Arrays that represent the initial binary number and the
    // expected one
    static int[] init, goal;
    static int size;        //number of nodes

    // Class used to represent the current state of a given node 
    static class State {
        /*
         * node is used to store the index of the current node
         * parent stores the index of the parent node
         * sel1 and sel2 are use to determine if a grandson has been already flipped
         */

        int node, parent;
        boolean sel1, sel2;

        // Simple constructor
        public State(int node, int parent, boolean sel1, boolean sel2) {
            this.node = node;
            this.parent = parent;
            this.sel1 = sel1;
            this.sel2 = sel2;
        }
    }

    public static void main(String[] args) throws IOException {

        //input
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(reader.readLine());       
        size = Integer.parseInt(st.nextToken());
        // Instantiates the Array of Lists, its size is "size + 1" because
        // we dont want to use the first position of the array
        tree = new List[size + 1];
        // Instantiates the Arrays which contains the initial and the goal numbers
        init = new int[size + 1];
        goal = new int[size + 1];

        // for each position on the Array of Lists a new List gets created
        for (int i = 0; i < tree.length; i++) {
            tree[i] = new ArrayList<>();
        }
        // Instantiates the List which is going to store the answer
        answer = new ArrayList<>();
        // We start to fill the tree.
        // Every position on the array is considered a node of the tree, each node
        // contains a list which stores his parent a his children
        for (int i = 1; i <= size - 1; i++) {
            st = new StringTokenizer(reader.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());

            tree[u].add(v);
            tree[v].add(u);
        }
        // Fills the input number
        st = new StringTokenizer(reader.readLine());
        for (int i = 1; i <= size; i++) {
            init[i] = Integer.parseInt(st.nextToken());
        }
        // Fills the goal number
        st = new StringTokenizer(reader.readLine());
        for (int i = 1; i <= size; i++) {
            goal[i] = Integer.parseInt(st.nextToken());
        }

        // Creates a stack to make a dfs
        Stack<State> stack = new Stack<>();
        // Creates the first state, the node is 1, his parent is -1(root)
        State current = new State(1, -1, false, false);

        stack.push(current);
        while (!stack.isEmpty()) {
            current = stack.pop();
            /*
             * If the goal and the init are different in the current node, and 
             * sel1 is equal to false, the he have to "flip" the number, if sel1 is 
             * equal to true, it means that the current node was already change by
             * his grand parent
             */
            if ((init[current.node] != goal[current.node] && !current.sel1)
                    || (init[current.node] == goal[current.node] && current.sel1)) {
                // if sel1 == false, then it becomes true, if sel1 == true it becomes false
                current.sel1 = !current.sel1;
                // We Add the flipped node to the answer list
                answer.add(current.node);
            }
            // Adds the children of the current node
            for (int i = 0; i < tree[current.node].size(); i++) {
                // every list stores the children and the parent, so if we are
                // in the parent, we dont want to add it to the stack
                if (current.parent == tree[current.node].get(i)) {
                    continue;
                }
                // The new state contains the son of the current node, and the
                // current becomes the father, we "flip" sel1 and sel2, to make 
                // sure the grandchildren get flipped
                stack.push(new State(tree[current.node].get(i), current.node, current.sel2, current.sel1));
            }
        }

        // Prints the number of nodes which were flipped
        int s = answer.size();
        System.out.println(s);

        // Prints every number on the answer
        for (int i = 0; i < s; i++) {
            System.out.println(answer.get(i));
        }
    }
}