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.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.Stack;


public class XorTreeStack {
    
    
    static List<Integer>[] tree;
    
    static List<Integer> out1;
     
    static int[] initial, finish;
    static int size;       

     
    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
        */
        public int node, parent;
        public boolean sel1, sel2;
        
        // 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) {

        //input
        Scanner sc = new Scanner(System.in);
        size = sc.nextInt();
        // 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];
        initial = new int[size + 1];
        finish = 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<>();
        }
        out1 = 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 ; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();

            tree[u].add(v);
            tree[v].add(u);
        }
        // Fills the input number
        for (int i = 1; i <= size; i++) {
            initial[i] = sc.nextInt();
        }
        // Fills the finish number
        for (int i = 1; i <= size; i++) {
            finish[i] = sc.nextInt();
        }       
        
        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 ((initial[current.node] != finish[current.node] && current.sel1 == false )
                    || (initial[current.node] == finish[current.node] && current.sel1 == true )) {
                
                if ( current.sel1 == false )
                    current.sel1 = true;
                else current.sel1 = false;
                // We Add the flipped node to the answer list
                out1.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 = out1.size();
        System.out.println(s);
        
        // Prints every number on the answer
        for (int i = 0; i < s; i++) {
            System.out.println(out1.get(i));
        }
    }
}