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;

/**
 * @author Daniel Roncancio This One is commented.
 * Seems like I've commented it, and now it doesn't work.
 */
public class XorTreeStack {

    //Array of lists. Each element of the array has a list.
    static List<Integer>[] tree;
    //List that contains the nodes which need to be flipped.
    static List<Integer> answer;
    //Initial indicates initial value of each node
    //Gooooooal is the target which we have to get to. World Cup style.
    static int[] initial, goooooal;
    //number of nodes
    static int size;

    //Inner class which designes the current State of a node. Similar to the past Position
    static class State {
        /*lukeSkyWalker is the node in which we are standing in.
         *darthVader is the parent of the node in which we are.
         *now and son are two integers which only take binary values (1 or 0) and are used
         *to determine if a grandson node has been flipped
         *I couldn't find any good names for 'now' or 'son'. I'm trying to be creative
         */

        public int lukeSkyWalker, darthVader, now, son;

        public State(int lukeSkyWalker, int darthVader, int now, int son) {
            this.lukeSkyWalker = lukeSkyWalker;
            this.darthVader = darthVader;
            this.now = now;
            this.son = son;
        }
    }

    //Had to put every other method in the main, 'cause it consumes time and time is actually something we don't have.
    public static void main(String[] args) {

        //Former input method, rest in peace
        Scanner sc = new Scanner(System.in);
        size = sc.nextInt();
        //Instanciates every array
        tree = new List[size + 1];
        initial = new int[size + 1];
        goooooal = new int[size + 1];   //we use size + 1 because we will start our array en [1] position

        for (int i = 0; i < tree.length; i++) {
            tree[i] = new ArrayList<>();
        }

        answer = new ArrayList<>();
        /*To fill the tree, we consider every position of the array as a node, and each
         *node contains a list that have the relation between the parent and its children.
         */
        for (int i = 1; i <= size - 1; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            //There you go.
            tree[u].add(v);
            tree[v].add(u);
        }
        //Input number
        for (int i = 1; i <= size; i++) {
            initial[i] = sc.nextInt();
        }
        //Goal number
        for (int i = 1; i <= size; i++) {
            goooooal[i] = sc.nextInt();
        }
        //Solver
        //We use a stack, to implement our knowledge of the course, even though we
        //could have also solve it with recursion, as I did in past codes.
        Stack<State> stack = new Stack<>();
        //Starts in node #1, with his parent as the root 
        State current = new State(1, -1, 0, 0);

        //Push first element into the stack
        stack.push(current);
        while (!stack.isEmpty()) {
            current = stack.pop();
            /*
             * If numbers of initial and goooal are different in the current node 
             * and now = 0 (initial case) the number gets flipped.
             * If now = 1 it means that the current node was already switched
             */
            if ((initial[current.lukeSkyWalker] != goooooal[current.lukeSkyWalker] && current.now == 0)
                    || (initial[current.lukeSkyWalker] == goooooal[current.lukeSkyWalker] && current.now == 1)) {
                //X-or operation. ^.^
                //Switches now value. If it's 0 -> 1, and viceversa.
                current.now ^= 1;
                //If flipped, to the stack
                answer.add(current.lukeSkyWalker);
            }
            //Add the current's node children
            for (int i = 0; i < (int) tree[current.lukeSkyWalker].size(); i++) {
                // If we are in the parent, we don't want to add it again, as we already did
                // because the list contains both parent and son
                if (current.darthVader == tree[current.lukeSkyWalker].get(i)) {
                    continue;
                }
                /* 1. Make new state with the son of the current node in it (next choice to check)
                 *  2. Make current node the parent
                 *  3. Switch now and son to make the grandsons flip
                 */
                stack.push(new State(tree[current.lukeSkyWalker].get(i), current.lukeSkyWalker, current.son, current.now));
            }
        }
        //Print number of nodes to be flipped
        int s = answer.size();
        System.out.println(s);
        //NO ITERATOR!!!! Makes the program slower!!!
        //Prints node to flip
        for (int i = 0; i < s; i++) {
            System.out.println(answer.get(i));
        }
    }
}