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 init_{i}, 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 goal_{i}, 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 ≤ 10^5). Each of the next n - 1 lines contains two integers u_{i} and v_{i} (1 ≤ u_{i}, v_{i} ≤ n; u_{i} ≠ v_{i}) meaning there is an edge between nodes u_{i} and v_{i}. 

The next line contains n integer numbers, the i-th of them corresponds to init_{i} (init_{i} is either 0 or 1). The following line also contains n integer numbers, the i-th number corresponds to goal_{i} (goal_{i} 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 x_{i}, representing that you pick a node x_{i}.


-----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

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = '# Target - Expert on CF\n# Be Humblefool\n\nimport sys\n\n# inf = float("inf")\nsys.setrecursionlimit(10000000)\n\n# abc=\'abcdefghijklmnopqrstuvwxyz\'\n# abd={\'a\': 0, \'b\': 1, \'c\': 2, \'d\': 3, \'e\': 4, \'f\': 5, \'g\': 6, \'h\': 7, \'i\': 8, \'j\': 9, \'k\': 10, \'l\': 11, \'m\': 12, \'n\': 13, \'o\': 14, \'p\': 15, \'q\': 16, \'r\': 17, \'s\': 18, \'t\': 19, \'u\': 20, \'v\': 21, \'w\': 22, \'x\': 23, \'y\': 24, \'z\': 25}\n# mod, MOD = 1000000007, 998244353\n# words = {1:\'one\',2:\'two\',3:\'three\',4:\'four\',5:\'five\',6:\'six\',7:\'seven\',8:\'eight\',9:\'nine\',10:\'ten\',11:\'eleven\',12:\'twelve\',13:\'thirteen\',14:\'fourteen\',15:\'quarter\',16:\'sixteen\',17:\'seventeen\',18:\'eighteen\',19:\'nineteen\',20:\'twenty\',21:\'twenty one\',22:\'twenty two\',23:\'twenty three\',24:\'twenty four\',25:\'twenty five\',26:\'twenty six\',27:\'twenty seven\',28:\'twenty eight\',29:\'twenty nine\',30:\'half\'}\n# vow=[\'a\',\'e\',\'i\',\'o\',\'u\']\n# dx,dy=[0,1,0,-1],[1,0,-1,0]\n\n# import random\nfrom collections import deque, Counter, OrderedDict,defaultdict\n# from heapq import nsmallest, nlargest, heapify,heappop ,heappush, heapreplace\n# from math import ceil,floor,log,sqrt,factorial,pi,gcd\n# from bisect import bisect,bisect_left,bisect_right,insort,insort_left,insort_right\n\ndef get_array(): return list(map(int, sys.stdin.readline().strip().split()))\ndef get_ints(): return map(int, sys.stdin.readline().strip().split())\ndef input(): return sys.stdin.readline().strip()\n\ndef dfs(current_node, xor, change_zero, change_one):\n    stack = [(current_node,xor,change_zero,change_one)]\n    nonlocal visited,ans,store\n\n    while stack:\n        current_node,xor,change_zero,change_one = stack.pop()\n        visited[current_node-1] = True\n        if xor==0:\n            if change[current_node-1]!=current[current_node-1]:\n                if ~change_zero&1:\n                    change_zero+=1\n                    ans+=1\n                    store.append(current_node)\n            else:\n                if change_zero&1:\n                    change_zero+=1\n                    ans+=1\n                    store.append(current_node)\n        else:\n            if change[current_node-1]!=current[current_node-1]:\n                if ~change_one&1:\n                    change_one+=1\n                    ans+=1\n                    store.append(current_node)\n            else:\n                if change_one&1:\n                    change_one+=1\n                    ans+=1\n                    store.append(current_node)\n        new_xor = xor^1\n        for child in mydict[current_node]:\n            if not visited[child-1]:\n                stack.append((child, new_xor, change_zero, change_one))\n\n\n\n\nn = int(input())\nmydict = defaultdict(list)\nfor i in range(n-1):\n    x,y = get_ints()\n    mydict[x].append(y)\n    mydict[y].append(x)\n\ncurrent = get_array()\nchange = get_array()\n\n# change_zero,change_one = 0,0\nans = 0\ncurrent_node = 1\nstore = []\nvisited = [False]*(n)\ndfs(current_node,1,0,0)\nprint(ans)\nfor i in store:\n    print(i)'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: