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:
/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */

/**
 *
 * @author CIRO
 */

import java.io.*;
import java.util.*;

public class XorTree {
    
    static class Node{
        int id, parentId, par, impar, altura;
        List<Integer> children = new ArrayList<>();
        Node(int id, int parent){
            this.id = id;
            this.parentId = parent;
        }   
    }
    
    public static boolean checkNode(Node[] a, int c, Integer[] g, int n){ 
        //metodo que verifica el valor actual del nodo con respecto a la salida
        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, se convierte en 1
            a[c].id = 1;
        else
            a[c].id = 0;//en caso contrario, se convierte en 0
    }
     
    public static boolean finish(Node[] a, Integer[] g, int n){ 
        //metodo para comprobar si los valores de el arbol conciden con los finales
        for(int i = 0; i<n; i++) //recorre el arreglo
            if ( a[i].id != g[i] ) //compara elemento a elemento el arreglo con los valores finales
                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
    }

    
    
    public static void main(String[] args) throws IOException {
        
        Scanner sc = new Scanner( System.in );
        int n = sc.nextInt();
        // se inicializa arreglo de n nodos, o el aarbol en si
        Node[] nodes = new Node[n]; 
        // el nodo 1 siempre es la raiz del arbol
        nodes[0] = new Node(1,-1); 
        //nodo raiz es la altura 0 del arbol
        nodes[0].altura = 0; 
        
        int numeroMovimientos = 0; //contador para num de flips utilizados
        
        for (int i = 0; i < n-1; i++) {
            //lectura de datos iniciales como datos finales
            int a = sc.nextInt(); 
            int b = sc.nextInt(); 
            if(nodes[a-1] != null) { 
                //asignacion de a como padre de b
                nodes[b-1] = new Node(b-1, a-1); 
                //la altura del nuevo nodo es 1 mas que la altura de su padre
                nodes[b-1].altura = nodes[a-1].altura + 1; 
                //se añade b en la lista de hijos de a
                nodes[a-1].children.add(b-1); 
            } else if(nodes[b-1] != null){ 
                //asignacion de b como padre de a
                nodes[a-1] = new Node(a-1, b-1); 
                //la altura del nuevo nodo es 1 mas que la altura de su padre
                nodes[a-1].altura = nodes[b-1].altura + 1; 
                //se añade a en la lista de hijos de b
                nodes[b-1].children.add(a-1); 
            } else {
                throw new RuntimeException();
            }
        }
        
        for(int i = 0; i < n; i++){
            //asignar estado inicial para cada nodo
            nodes[i].id = sc.nextInt(); 
        }
        
        Integer[] finishValues = new Integer[n];
        for(int i=0; i<n; i++){
            //asignar estado final para cada nodo
            finishValues[i] = sc.nextInt(); 
        }
        
        //lista para almacenar nodos que hayan cambiado
        List<Integer> flippedNodes = new ArrayList<Integer>(); 
        //cola para almacenar nodos temporalmente
        Queue queue = new LinkedList(); 
        //se agregan la lista de hijos del nodo raiz
        queue.add(nodes[0].children); 
        
        if( checkNode(nodes,0, finishValues, 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;
                //incrementa contador del num de movimientos
                numeroMovimientos++;
                //añade el nodo intercambiado a la cola de respuesta
                flippedNodes.add(1);       
        }
        else{   
                nodes[0].par = 0;
                nodes[0].impar = 0;
        }
        
        // si la cola NO esta vacia
        while ( !queue.isEmpty() ){ 
            //lista de enteros para recorrer los hijos de cada nodo
            List<Integer> child = (List)queue.remove();
                for(int i=0; i < child.size(); i++){ //recorre la lista de hijos obtenida de la cola.
                    //si el nodo i tiene hijos, entra
                    if(nodes[child.get(i)].children.size() > 0) 
                        //añade la lista de hijos del nodo i a la cola
                        queue.add(nodes[child.get(i)].children); 

                    //hereda variable control de cambios en los niveles pares
                    nodes[child.get(i)].par = nodes[nodes[child.get(i)].parentId].par; 
                    //hereda variable control de cambios en los niveles impares
                    nodes[child.get(i)].impar = nodes[nodes[child.get(i)].parentId].impar; 
                    
                    //nodo de altura par && NO hay un numero par de cambios, el nodo SI necesita "flip"
                    if( nodes[child.get(i)].altura% 2 == 0 && nodes[child.get(i)].par%2 == 1)
                        flip(nodes,child.get(i));
                                        
                    else if( nodes[child.get(i)].altura% 2 == 1 && nodes[child.get(i)].impar%2 == 1)
                        flip(nodes,child.get(i));
                    
                    if( checkNode(nodes,child.get(i),finishValues,n) ){
                        if(nodes[child.get(i)].altura% 2 == 0){ //Nivel par
                            nodes[child.get(i)].par++;
                            flip(nodes,child.get(i));
                        }
                        else{ //Nivel impar
                            nodes[child.get(i)].impar++;
                            flip(nodes,child.get(i));
                        }
                        numeroMovimientos++;
                        flippedNodes.add(child.get(i)+1);
                    }
                } 
        }
        System.out.println(numeroMovimientos);     
        StringBuilder sb = new StringBuilder();
        for (Integer ansNode : flippedNodes) {
            sb.append(ansNode).append("\n");
        }
        System.out.println(sb);
    }
    
}