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.*;
public class XorTree{

    //Lista "arbol" que contendra unas listas de arreglos.
    static   List<List<Integer>> arbol = new ArrayList<List<Integer>>();
    //Lista que contiene los nodos que van a ser volteados.
    static List<Integer> volteados;
    //Arreglos que contienen la forma inicial y final del arbol .
    static int[] inicial, cambiado;
    //numero de nodos del arbol.
    static int size;
    //creamos la clase Estado que tendra el nodo actual, el nodo padre y
    //los estados de los nietos para saber si han sido volteados.
    static class Estado {
    //variables.
        public int nodoactual, nodopadre, actual, nieto;
        //cuando actual es = 0 no se han cambiado
        //Constructor debe tener el mismo nombre de la clase.
        public Estado(int nodoactual, int nodopadre, int actual, int nieto) {
            this.nodoactual = nodoactual;
            this.nodopadre = nodopadre;
            this.actual = actual;
            this.nieto = nieto;
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        size = sc.nextInt();
        inicial = new int[size];
        cambiado = new int[size];  
        for (int i = 0; i <= size; i++) {
            arbol.add(new ArrayList<Integer>());
        }
        volteados = new ArrayList<>();
        //cada posicion de nuestro arbol sera un nodo que contiene
        //la informacion del padre y los hijos
        for (int i = 1; i <= size - 1; i++) {
            int p = sc.nextInt();
            int s = sc.nextInt();
            //  Eso es
            arbol.get(p).add(s);//agrega v en la posicion u
            arbol.get(s).add(p);//agrega u en la posicion v
        }
        //Se llena el vector del arbol inicial
        for (int i = 0; i < size; i++) {
            inicial[i] = sc.nextInt();
        }
        //Se llena el vector del arbol final
        for (int i = 0; i < size; i++) {
            cambiado[i] = sc.nextInt();
        }
        //Para la solucion se tomo la desicion de utilizar una
        //pila.     
        Stack<Estado> stack = new Stack<>();
        //Comienza en el nodo 1, con su padre como la raiz, actual y nieto se
        //inician con 0
        Estado estado = new Estado(1, -1, 0, 0);
        //ingreso el primer elemento a la pila
        stack.push(estado);
        while (!stack.isEmpty()) {
            estado = stack.pop();
            //voy sacando los estados (estado) de los nodos para irlos analizando
            if ((inicial[estado.nodoactual-1] != cambiado[estado.nodoactual-1] && estado.actual == 0)
                    || (inicial[estado.nodoactual-1] == cambiado[estado.nodoactual-1] && estado.actual == 1)) {
                //si los dos son iguales pero actual es 1 ya fueron cambiados y por ello se meten en la
                //pila, tambien si son diferentes y actual es cero osea no han sido cambiados, se meten en la
                //pila y se les hace el xor.
                //Se realiza la operacion de cambio con el XOR 1-->0 o 0-->1
                estado.actual ^= 1;//Operacion Xor
                //Se guarda en la pila de cambiados
                volteados.add(estado.nodoactual);
            }
            //
            for (int i = 0; i < arbol.get(estado.nodoactual).size(); i++) {
                //Ahora debemos verificar los nietos para lo cual el nodopadre
                //lo movemos a el nodoactual, para mirar la siguiente
                //opcion de cambio
                if (estado.nodopadre ==
                arbol.get(estado.nodoactual).get(i)) {
                    continue;
                }
               //generamos un nuevo estado en la pila con nodoactual=siguiente nodo;nodopadre=nodoactual;actual=nieto;nieto=actual
               stack.push(new Estado(arbol.get(estado.nodoactual).get(i), estado.nodoactual, estado.nieto, estado.actual));
            }
        }
        //Imprime el numero de nodos que fueron cambiados
        System.out.println(volteados.size());
        //Imprime los elementos dentro del Arraylist volteados que son los
        //nodos que fueron cambiados
        for (int i = 0; i < volteados.size(); i++) {
            System.out.println(volteados.get(i));
        }
    }
}