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.*;
import java.util.*;

@SuppressWarnings("unchecked")
public class D {

    static class Node{
        int id, parent, par, impar, generacion;
        List<Integer> children = new ArrayList<Integer>();
        Node(int id, int parent){
            this.id = id;
            this.parent = parent;
        }
    }

    public static void main(String[] args) throws IOException {
         Scanner sc = new Scanner( System.in );
         int n = sc.nextInt();
         Node[] nodes = new Node[n]; // se inicializa arreglo de n nodos
         nodes[0] = new Node(1,-1); // el nodo 1 siempre es la raiz del arbol
         nodes[0].generacion = 0; //nodo raiz es la generacion 0 del arbol
         for (int i = 0; i < n-1; i++) {
            int a = sc.nextInt(); //lectura de pareja de datos 
            int b = sc.nextInt();
            if(nodes[a-1] != null) { 
                nodes[b-1] = new Node(b-1, a-1); //asignacion de a como padre de b
                nodes[b-1].generacion = nodes[a-1].generacion + 1; //la generacion del nuevo nodo es 1 mas que la generacion de su padre
                nodes[a-1].children.add(b-1); //se añade b en la lista de hijos de a
            } else if(nodes[b-1] != null){ 
                nodes[a-1] = new Node(a-1, b-1); //asignacion de b como padre de a
                nodes[a-1].generacion = nodes[b-1].generacion + 1; //la generacion del nuevo nodo es 1 mas que la generacion de su padre
                nodes[b-1].children.add(a-1); //se añade a en la lista de hijos de b
            } else {
                throw new RuntimeException();
            }
        }               
        int numMov = 0; //contador para num de flips utilizados
        for(int i=0; i<n; i++){
            nodes[i].id = sc.nextInt(); //asignar estado inicial cada nodo
        }
        
        Integer[] goal = new Integer[n];
        for(int i=0; i<n; i++){
            goal[i] = sc.nextInt(); //lectura estado final deseado
        }
        
        List<Integer> ansNodes = new ArrayList<Integer>(); //lista para almacenar nodos cuyo valor cambio
        Queue queue = new LinkedList(); //cola para almacenar nodos temporalmente
        queue.add(nodes[0].children); //se agregan la lista de hijos del nodo raiz
        
        if( checkNode(nodes,0, goal, n) ){ //si el valor de la raiz es diferente al valor deseado, cambia su valor
                flip(nodes,0);
                nodes[0].par = 1;
                nodes[0].impar = 0;
                numMov++;           //incrementa contador del num de movimientos
                ansNodes.add(1);        //añade el nodo intercambiado a la cola de respuesta
        }
        else{   
                nodes[0].par = 0;
                nodes[0].impar = 0;
        }
        
        
        while ( !queue.isEmpty() ){  // si la cola no esta vacia
            List<Integer> child = (List)queue.remove(); //lista de enteros para recorrer los hijos de cada nodo
                for(int i=0; i < child.size(); i++){ //recorre la lista de hijos obtenida de la cola.
                    if(nodes[child.get(i)].children.size() > 0) //si el nodo i tiene hijos, entra
                        queue.add(nodes[child.get(i)].children); //añade la lista de hijos del nodo i a la cola

                    nodes[child.get(i)].par = nodes[nodes[child.get(i)].parent].par; //hereda variable control de cambios en las generaciones pares
                    nodes[child.get(i)].impar = nodes[nodes[child.get(i)].parent].impar; //hereda variable control de cambios en las generaciones impares
                    
                    if( nodes[child.get(i)].generacion% 2 == 0 && nodes[child.get(i)].par%2 == 1)//nodo de generacion par && NO hay un numero par de cambios, el nodo SI necesita "flip"
                        flip(nodes,child.get(i));
                                        
                    else if( nodes[child.get(i)].generacion% 2 == 1 && nodes[child.get(i)].impar%2 == 1)
                        flip(nodes,child.get(i));
                    
                    if( checkNode(nodes,child.get(i),goal,n) ){
                        if(nodes[child.get(i)].generacion% 2 == 0){ //generacion par
                            nodes[child.get(i)].par++;
                            flip(nodes,child.get(i));
                        }
                        else{ //generacion impar
                            nodes[child.get(i)].impar++;
                            flip(nodes,child.get(i));
                        }
                        numMov++;
                        ansNodes.add(child.get(i)+1);
                    }
                }
                
        }
        System.out.println(numMov);     
        StringBuilder sb = new StringBuilder();
        for (Integer ansNode : ansNodes) {
            sb.append(ansNode).append("\n");
        }
        System.out.println(sb);        
    }
    
    public static boolean checkNode(Node[] a, int c, Integer[] g, int n){ //metodo para compara estado de un nodo c con respecto a la salida deseada
        if(a[c].id != g[c]) //si el valor del nodo es diferente al de goal, entra
            return true;
        return false;
    }

    public static void flip(Node[] a, int c){
        if(a[c].id == 0) //si el nodo es 0, su nuevo valor es 1
            a[c].id = 1;
        else
            a[c].id = 0;//en caso contrario, su nuevo valor es 0
    }
    
    public static boolean finish(Node[] a, Integer[] g, int n){ //metodo para comprobar si los valores del nodo ya son iguales a los esperados(goal)
        for(int i = 0; i<n; i++) //recorre el arreglo
            if ( a[i].id != g[i] ) //compara elemento a elemento el arreglo con el arreglo de salida esperada (goal)
                return false; //si al menos un elemento es diferente al valor esperado, retorna falso
        return true; // si termina el ciclo, indica que todos los nodos son iguales, y devuelve verdadero
    }
}