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

Source: codeforces | Difficulty: EASY
Tags: Tree algorithms

Graph traversal


Solutions:
intin = lambda : list(map(int, input().split()))
iin = lambda : int(input())
Ain = lambda : list(map(int, input().split()))
from queue import LifoQueue
mod = 1000000007
n = iin()
m = n + 1
v = [[] for i in range(m)]
p = [0] * m
for _ in range(n - 1):
	(a, b) = intin()
	v[a].append(b)
	v[b].append(a)
vis = [False] * m
flipped = [0] * m
flip = [0] * m
ans = []

def dfs(root):
	q = [root]
	while len(q) > 0:
		node = q.pop()
		vis[node] = True
		flipped[node] = flipped[p[p[node]]]
		if flipped[node] != flip[node]:
			flipped[node] ^= 1
			ans.append(node)
		for i in range(len(v[node])):
			son = v[node][i]
			if not vis[son]:
				q.append(son)
				p[son] = node
a = Ain()
b = Ain()
for i in range(n):
	flip[i + 1] = a[i] ^ b[i]
dfs(1)
print(len(ans))
for i in range(len(ans)):
	print(ans[i])


import sys

def dfs(tree, root, priv_root, cur_lvl, priv_lvl, diff, pick_list):
	if not tree:
		return
	stack = [(root, priv_root, cur_lvl, priv_lvl)]
	while stack:
		(root, priv_root, cur_lvl, priv_lvl) = stack.pop()
		if cur_lvl ^ diff[root]:
			cur_lvl ^= 1
			pick_list.append(str(root))
		stack += [(vertex, root, priv_lvl, cur_lvl) for vertex in tree[root] if vertex != priv_root]

def main():
	n = int(input())
	tree = dict()
	for _ in range(n - 1):
		(u, v) = [int(x) for x in input().split()]
		tree[u] = tree.get(u, set()) | set([v])
		tree[v] = tree.get(v, set()) | set([u])
	init = [0] + [int(x) for x in input().split()]
	goal = [0] + [int(x) for x in input().split()]
	diff = [i ^ j for (i, j) in zip(init, goal)]
	pick_list = list()
	dfs(tree, 1, 0, 0, 0, diff, pick_list)
	num = len(pick_list)
	print(num)
	if num:
		print('\n'.join(pick_list))
sys.exit(main())


from collections import defaultdict, deque, Counter, OrderedDict
import sys

def main():
	n = int(input())
	adj = [[] for i in range(n + 1)]
	for i in range(n - 1):
		(a, b) = map(int, input().split())
		(a, b) = (a - 1, b - 1)
		adj[a].append(b)
		adj[b].append(a)
	init = [int(i) for i in input().split()]
	goal = [int(i) for i in input().split()]
	visited = [0] * n
	par = [[] for i in range(n)]
	dq = deque()
	dq.append((0, 0))
	while len(dq) > 0:
		(s, p) = dq.pop()
		if visited[s]:
			continue
		visited[s] = 1
		par[p].append(s)
		for i in adj[s]:
			dq.append((i, s))
	par[0] = par[0][1:]
	ans = []
	dq = deque()
	dq.append((0, 0, 0, 0))
	while len(dq) > 0:
		(s, l, fo, fe) = dq.pop()
		if l % 2 == 0:
			if fe % 2 == 1:
				init[s] = 1 - init[s]
		elif fo % 2 == 1:
			init[s] = 1 - init[s]
		if init[s] != goal[s]:
			ans.append(s + 1)
			if l % 2:
				fo += 1
			else:
				fe += 1
		for j in par[s]:
			dq.append((j, l + 1, fo, fe))
	print(len(ans))
	print('\n'.join(map(str, ans)))

def __starting_point():
	main()
__starting_point()


n = int(input())
g = [[] for i in range(n)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	g[a - 1].append(b - 1)
	g[b - 1].append(a - 1)
start = list(map(int, input().split()))
goal = list(map(int, input().split()))
q = [(0, 0, 0, 0)]
ans = []
while q:
	(node, dst, a, b) = q.pop()
	if dst:
		if a != (start[node] != goal[node]):
			ans.append(node + 1)
			a = 1 - a
	elif b != (start[node] != goal[node]):
		ans.append(node + 1)
		b = 1 - b
	dst = 1 - dst
	for to in g[node]:
		g[to].remove(node)
		q.append((to, dst, a, b))
print(len(ans))
print('\n'.join(map(str, ans)))


import sys
readline = sys.stdin.readline

def i1():
	return int(readline())

def nl():
	return [int(s) for s in readline().split()]

def nn(n):
	return [int(readline()) for i in range(n)]

def nnp(n, x):
	return [int(readline()) + x for i in range(n)]

def nmp(n, x):
	return (int(readline()) + x for i in range(n))

def nlp(x):
	return [int(s) + x for s in readline().split()]

def nll(n):
	return [[int(s) for s in readline().split()] for i in range(n)]

def mll(n):
	return ([int(s) for s in readline().split()] for i in range(n))

def s1():
	return readline().rstrip()

def sl():
	return [s for s in readline().split()]

def sn(n):
	return [readline().rstrip() for i in range(n)]

def sm(n):
	return (readline().rstrip() for i in range(n))

def redir(s):
	global readline
	import os
	fn = sys.argv[0] + f'/../in-{s}.txt'
	readline = open(fn).readline if os.path.exists(fn) else readline
redir('a')
n = i1()
nodes = [[] for i in range(n + 1)]
for i in range(n - 1):
	(u, v) = nl()
	nodes[u].append(v)
	nodes[v].append(u)
init = [0] + nl()
goal = [0] + nl()
roots = [1]
flip = [[0] * (n + 1), [0] * (n + 1)]
fa = [0] * (n + 1)
fa[1] = 1
level = 0
m = []
while roots:
	_roots = []
	fli = flip[level % 2]
	for r in roots:
		f = fli[fa[fa[r]]]
		if f ^ init[r] != goal[r]:
			f = 1 - f
			m.append(r)
		fli[r] = f
		for i in nodes[r]:
			if fa[i] == 0:
				_roots.append(i)
				fa[i] = r
	roots = _roots
	level += 1
init[0] = goal[0] = None
print(len(m))
print('\n'.join((str(i) for i in m)))


__author__ = 'artyom'

def read_int():
	return int(input())

def read_int_ary():
	return map(int, input().split())
n = read_int()
g = [[] for x in range(n + 1)]
for i in range(n - 1):
	(u, v) = read_int_ary()
	g[u].append(v)
	g[v].append(u)
init = [0] + list(read_int_ary())
goal = [0] + list(read_int_ary())
s = []

def solve(graph, start):
	stack = [(start, -1, [1, 1], 0)]
	while stack:
		params = stack.pop(-1)
		node = params[0]
		parent = params[1]
		st = list(params[2])
		sign = params[3]
		if init[node] ^ st[sign] == goal[node]:
			s.append(node)
			st[sign] = 1 - st[sign]
		sign = 1 - sign
		for child in graph[node]:
			if child != parent:
				stack.append((child, node, st, sign))
solve(g, 1)
print(len(s))
for v in s:
	print(v)


from sys import stdin, stdout
n = int(input())
a = [[] for i in range(n)]
for i in range(n - 1):
	(c, d) = (int(o) for o in stdin.readline().split())
	a[c - 1].append(d - 1)
	a[d - 1].append(c - 1)
b = list((int(o) for o in stdin.readline().split()))
c = list((int(o) for o in stdin.readline().split()))
lv = [0] * n
lv[0] = 1
q = [0]
while len(q) != 0:
	r = q.pop()
	for i in a[r]:
		if lv[i] == 0:
			lv[i] = lv[r] + 1
			q.append(i)
ans = ''
vis = [True] * n
vis[0] = False
k = 0
if b[0] == c[0]:
	q = [(0, 0, 0)]
else:
	q = [(0, 1, 0)]
	ans += '1' + '\n'
	k += 1
while len(q) != 0:
	(no, o, e) = q.pop()
	for i in a[no]:
		if vis[i]:
			l = e
			m = o
			vis[i] = False
			if lv[i] % 2 == 0:
				if b[i] == c[i] and l % 2 != 0:
					ans += str(i + 1) + '\n'
					l += 1
					k += 1
				elif b[i] != c[i] and l % 2 == 0:
					ans += str(i + 1) + '\n'
					l += 1
					k += 1
			elif b[i] == c[i] and m % 2 != 0:
				ans += str(i + 1) + '\n'
				m += 1
				k += 1
			elif b[i] != c[i] and m % 2 == 0:
				ans += str(i + 1) + '\n'
				m += 1
				k += 1
			q.append((i, m, l))
print(k)
stdout.write(ans)


from collections import defaultdict
n = int(input())
d = defaultdict(list)

def DFSop(d1, x, goal, state, visited):
	c = 0
	stack = [(x, c)]
	l = []
	while len(stack):
		(temp, c) = stack.pop()
		visited[temp] = 1
		if c % 2 == 1:
			state[temp - 1] = 1 - state[temp - 1]
		if state[temp - 1] != goal[temp - 1]:
			c = c + 1
			state[temp - 1] = goal[temp - 1]
			l.append(temp)
		for i in d1[temp]:
			if visited[i] == 0:
				stack.append((i, c))
	return l

def DFS(d, x, parent, visited):
	stack = [(x, 0)]
	d1 = defaultdict(list)
	while len(stack):
		(temp, parent) = stack.pop()
		visited[temp] = 1
		for i in d[temp]:
			if visited[i] == 0:
				d1[parent].append(i)
				stack.append((i, temp))
	return d1
for i in range(n - 1):
	(a, b) = map(int, input().split())
	d[a].append(b)
	d[b].append(a)
parent = 0
visited = [0 for i in range(n + 1)]
x = 1
state = list(map(int, input().split()))
goal = list(map(int, input().split()))
c = 0
x = 1
parent = 0
d1 = DFS(d, x, parent, visited)
visited = [0 for i in range(n + 1)]
l = []
ans = DFSop(d1, x, goal, state, visited)
for i in d[1]:
	ans = ans + DFSop(d1, i, goal, state, visited)
ans = set(ans)
print(len(ans))
for i in ans:
	print(i)


bot = True
n = int(input())
p = [[] for i in range(n + 1)]
for i in range(n - 1):
	(a, b) = list(map(int, input().split()))
	p[a].append(b)
	p[b].append(a)
(u, v) = (' ' + input()[::2], ' ' + input()[::2])
(s, q) = ([(1, 0, 0, 0)], [])
while s:
	(a, k, i, j) = s.pop()
	if k:
		if i != (u[a] != v[a]):
			q.append(a)
			i = 1 - i
	elif j != (u[a] != v[a]):
		q.append(a)
		j = 1 - j
	k = 1 - k
	for b in p[a]:
		p[b].remove(a)
		s.append((b, k, i, j))
print(len(q))
print('\n'.join(map(str, q)))


from collections import defaultdict, deque, Counter, OrderedDict
from bisect import insort, bisect_right, bisect_left
import threading, sys

def main():
	n = int(input())
	adj = [[] for i in range(n + 1)]
	for i in range(n - 1):
		(a, b) = list(map(int, input().split()))
		(a, b) = (a - 1, b - 1)
		adj[a].append(b)
		adj[b].append(a)
	init = [int(i) for i in input().split()]
	goal = [int(i) for i in input().split()]
	visited = [0] * n
	par = [[] for i in range(n)]

	def dfs(s, p):
		if visited[s]:
			return
		visited[s] = 1
		par[p].append(s)
		for i in adj[s]:
			dfs(i, s)
	dfs(0, 0)
	par[0] = par[0][1:]
	ans = []

	def dfs2(s, l, fo, fe):
		if l % 2 == 0:
			if fe % 2 == 1:
				init[s] = 1 - init[s]
		elif fo % 2 == 1:
			init[s] = 1 - init[s]
		if init[s] != goal[s]:
			ans.append(s + 1)
			if l % 2:
				fo += 1
			else:
				fe += 1
		for j in par[s]:
			dfs2(j, l + 1, fo, fe)
	dfs2(0, 0, 0, 0)
	print(len(ans))
	print('\n'.join(map(str, ans)))

def __starting_point():
	sys.setrecursionlimit(400000)
	threading.stack_size(102400000)
	thread = threading.Thread(target=main)
	thread.start()
__starting_point()


from collections import defaultdict, deque, Counter, OrderedDict
from bisect import insort, bisect_right, bisect_left
import threading

def main():
	n = int(input())
	adj = [[] for i in range(n + 1)]
	for i in range(n - 1):
		(a, b) = map(int, input().split())
		(a, b) = (a - 1, b - 1)
		adj[a].append(b)
		adj[b].append(a)
	init = [int(i) for i in input().split()]
	goal = [int(i) for i in input().split()]
	visited = [0] * n
	par = [[] for i in range(n)]
	dq = deque()
	dq.append((0, 0))
	while len(dq) > 0:
		(s, p) = dq.pop()
		if visited[s]:
			continue
		visited[s] = 1
		par[p].append(s)
		for i in adj[s]:
			dq.append((i, s))
	par[0] = par[0][1:]
	ans = []
	dq = deque()
	dq.append((0, 0, 0, 0))
	while len(dq) > 0:
		(s, l, fo, fe) = dq.pop()
		if l % 2 == 0:
			if fe % 2 == 1:
				init[s] = 1 - init[s]
		elif fo % 2 == 1:
			init[s] = 1 - init[s]
		if init[s] != goal[s]:
			ans.append(s + 1)
			if l % 2:
				fo += 1
			else:
				fe += 1
		for j in par[s]:
			dq.append((j, l + 1, fo, fe))
	print(len(ans))
	print('\n'.join(map(str, ans)))
thread = threading.Thread(target=main)
thread.start()


n = int(input())
L = [[] for i in range(n)]
for i in range(n - 1):
	(a, b) = list(map(int, input().split()))
	L[a - 1].append(b - 1)
	L[b - 1].append(a - 1)
l = list(map(int, input().split()))
l1 = list(map(int, input().split()))
W = []
for i in range(n):
	W.append(abs(l[i] - l1[i]))
was = [0 for i in range(n)]
q = [[0, 0, 0]]
ans = []
while q:
	e = q[0]
	was[e[0]] = 1
	if e[1] != W[e[0]]:
		ans.append(e[0] + 1)
		e[1] = 1 - e[1]
	for x in L[e[0]]:
		if was[x] == 0:
			q.append([x, e[2], e[1]])
	del q[0]
print(len(ans))
print('\n'.join(map(str, ans)))


from sys import stdin, stdout, setrecursionlimit
import heapq
from math import gcd, ceil, sqrt
from collections import Counter, deque
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations
ii1 = lambda : int(stdin.readline().strip())
is1 = lambda : stdin.readline().strip()
iia = lambda : list(map(int, stdin.readline().strip().split()))
isa = lambda : stdin.readline().strip().split()
setrecursionlimit(100000)
mod = 1000000007

def getAns(init, goal, d):
	queue = deque([[0, -1, 0, 0, 0]])
	seen = set()
	ans = []
	while len(queue):
		(cur, par, xor0, xor1, depth) = queue.popleft()
		if cur not in seen:
			seen.add(cur)
			if init[cur] ^ xor0 != goal[cur] and depth == 0:
				ans.append(cur + 1)
				xor0 ^= 1
			if init[cur] ^ xor1 != goal[cur] and depth == 1:
				ans.append(cur + 1)
				xor1 ^= 1
			for neigh in d.get(cur, []):
				queue.append([neigh, cur, xor0, xor1, depth ^ 1])
	return ans
n = ii1()
d = {}
for i in range(n - 1):
	(a, b) = iia()
	d.setdefault(a - 1, []).append(b - 1)
	d.setdefault(b - 1, []).append(a - 1)
init = iia()
goal = iia()
ans = getAns(init, goal, d)
print(len(ans))
for i in ans:
	print(i)


import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import *
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
import copy
import time
starttime = time.time()
mod = int(pow(10, 9) + 7)
mod2 = 998244353

def data():
	return sys.stdin.readline().strip()

def out(*var, end='\n'):
	sys.stdout.write(' '.join(map(str, var)) + end)

def L():
	return list(sp())

def sl():
	return list(ssp())

def sp():
	return map(int, data().split())

def ssp():
	return map(str, data().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(n, val) for j in range(m)]
try:
	sys.stdin = open('input.txt', 'r')
except:
	pass

def pmat(A):
	for ele in A:
		print(*ele, end='\n')

def seive():
	prime = [1 for i in range(10 ** 6 + 1)]
	prime[0] = 0
	prime[1] = 0
	for i in range(10 ** 6 + 1):
		if prime[i]:
			for j in range(2 * i, 10 ** 6 + 1, i):
				prime[j] = 0
	return prime
n = L()[0]
A = [L() for i in range(n - 1)]
g = [[] for i in range(n + 1)]
for (x, y) in A:
	g[x].append(y)
	g[y].append(x)
curr = L()
target = L()
q = deque()
q.append([1, 0, int(curr[0] != target[0])])
vis = [0 for i in range(n + 1)]
vis[1] = 1
turns = []
if curr[0] != target[0]:
	turns.append(1)
while q:
	(node, l2, l1) = q.popleft()
	for neigh in g[node]:
		if vis[neigh]:
			continue
		vis[neigh] = 1
		if (curr[neigh - 1] + l2) % 2 != target[neigh - 1]:
			turns.append(neigh)
			q.append([neigh, l1, (l2 + 1) % 2])
		else:
			q.append([neigh, l1, l2])
print(len(turns))
for ele in turns:
	print(ele)
endtime = time.time()


import sys
sys.setrecursionlimit(150000)
from collections import deque, Counter, OrderedDict, defaultdict

def get_array():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def input():
	return sys.stdin.readline().strip()

def dfs(current_node, xor, change_zero, change_one):
	stack = [(current_node, xor, change_zero, change_one)]
	nonlocal visited, ans, store
	while stack:
		(current_node, xor, change_zero, change_one) = stack.pop()
		visited[current_node - 1] = True
		if xor == 0:
			if change[current_node - 1] != current[current_node - 1]:
				if ~change_zero & 1:
					change_zero += 1
					ans += 1
					store.append(current_node)
			elif change_zero & 1:
				change_zero += 1
				ans += 1
				store.append(current_node)
		elif change[current_node - 1] != current[current_node - 1]:
			if ~change_one & 1:
				change_one += 1
				ans += 1
				store.append(current_node)
		elif change_one & 1:
			change_one += 1
			ans += 1
			store.append(current_node)
		new_xor = xor ^ 1
		for child in mydict[current_node]:
			if not visited[child - 1]:
				stack.append((child, new_xor, change_zero, change_one))
n = int(input())
mydict = defaultdict(list)
for i in range(n - 1):
	(x, y) = get_ints()
	mydict[x].append(y)
	mydict[y].append(x)
current = get_array()
change = get_array()
ans = 0
current_node = 1
store = []
visited = [False] * n
dfs(current_node, 1, 0, 0)
print(ans)
for i in store:
	print(i)


from collections import deque
stack = deque()
n = int(input())
links = [tuple(map(lambda x: int(x) - 1, input().split())) for i in range(n - 1)]
linked_to = [[] for i in range(n)]
for (x, y) in links:
	linked_to[x].append(y)
	linked_to[y].append(x)
init = list(map(lambda x: x == '1', input().split()))
goal = list(map(lambda x: x == '1', input().split()))
stack.append(0)
ops = 0
visited = [False] * n
parent = [n] * (n + 1)
was_swapped = [False] * (n + 1)
visited[0] = True

def xor(x, y):
	return x != y

def get_chld(i):
	for e in linked_to[i]:
		if e != parent[i]:
			yield e
while len(stack) > 0:
	c = stack.pop()
	for l in linked_to[c]:
		if not visited[l]:
			visited[l] = True
			parent[l] = c
			stack.append(l)
chosen = []
stack.append(0)
while len(stack) > 0:
	c = stack.pop()
	stack.extend(get_chld(c))
	was_swapped[c] = was_swapped[parent[parent[c]]]
	if xor(xor(init[c], goal[c]), was_swapped[c]):
		was_swapped[c] = not was_swapped[c]
		ops += 1
		chosen.append(c + 1)
print(ops, *chosen, sep='\n')


N = int(100000.0 + 3)
n = int(input())
adj = list(([] for i in range(N)))
for _ in range(n - 1):
	(u, v) = list(map(int, input().split()))
	adj[u].append(v)
	adj[v].append(u)
a = [0] + list(map(int, input().split()))
b = [0] + list(map(int, input().split()))

def dfs(u, p, c_lvl, p_lvl, d):
	stk = [(u, p, c_lvl, p_lvl)]
	while stk:
		(u, p, c_lvl, p_lvl) = stk.pop()
		if c_lvl != d[u]:
			c_lvl = 1 - c_lvl
			res.append(str(u))
		for v in adj[u]:
			if v != p:
				stk += [(v, u, p_lvl, c_lvl)]
d = [i ^ j for (i, j) in zip(a, b)]
res = []
dfs(1, 0, 0, 0, d)
print(len(res))
print('\n'.join(res))


from sys import stdin, setrecursionlimit
from collections import defaultdict
setrecursionlimit(1500000)

def counter(num):
	if num == 0:
		return 1
	else:
		return 0

def flip_me(original, count, index):
	if count % 2 == 0:
		return original[index]
	else:
		return counter(original[index])

def dfs(graph, visited, ans, original, goal, change, node, dfs_stack):
	dfs_stack.append(node)
	while len(dfs_stack) > 0:
		node = dfs_stack.pop()
		visited[node] = True
		value = flip_me(original, change[node], node - 1)
		add = 0
		if goal[node - 1] == value:
			pass
		else:
			add = 1
			ans[node] = True
		flag = 0
		for i in graph[node]:
			if visited[i] == False:
				flag = 1
				for j in graph[i]:
					if visited[j] == False:
						change[j] += change[node] + add
				dfs_stack.append(node)
				dfs_stack.append(i)
				break
		if flag == 0:
			pass

def calculate(graph, original, goal, n):
	visited = dict()
	change = dict()
	for i in range(1, n + 1):
		visited[i] = False
		change[i] = 0
	ans = dict()
	dfs_stack = []
	dfs(graph, visited, ans, original, goal, change, 1, dfs_stack)
	return ans
n = int(stdin.readline().strip())
graph = defaultdict(list)
for i in range(1, n + 1):
	graph[i]
for _ in range(n - 1):
	(u, v) = list(map(int, stdin.readline().split()))
	graph[u].append(v)
	graph[v].append(u)
original = list(map(int, stdin.readline().split()))
goal = list(map(int, stdin.readline().split()))
count = [0]
ans = calculate(graph, original, goal, n)
print(len(ans))
for i in ans:
	print(i)


def main():
	n = int(input())
	l = [[] for _ in range(n + 1)]
	for _ in range(n - 1):
		(u, v) = list(map(int, input().split()))
		l[u].append(v)
		l[v].append(u)
	sw = [a != b for (a, b) in zip(input()[::2], input()[::2])]
	root = (1, False, False)
	(nxt, res, avail) = ([root], [0], [True] * (n + 1))
	while nxt:
		(cur, nxt) = (nxt, [])
		for (v, a, b) in cur:
			if sw[v - 1] != a:
				a = not a
				res.append(v)
			avail[v] = False
			for u in l[v]:
				if avail[u]:
					nxt.append((u, b, a))
	res[0] = len(res) - 1
	print('\n'.join(map(str, res)))

def __starting_point():
	main()
__starting_point()


n = int(input())
adj = [[] for i in range(n + 1)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	adj[a].append(b)
	adj[b].append(a)
u = [-1] + list(map(int, input().split()))
v = [-1] + list(map(int, input().split()))
q = [(1, 0, 0, 0)]
ans = []
while q:
	(x, a, b, c) = q.pop()
	if a:
		if b != (u[x] != v[x]):
			ans.append(x)
			b = 1 - b
	elif c != (u[x] != v[x]):
		ans.append(x)
		c = 1 - c
	a = 1 - a
	for i in adj[x]:
		adj[i].remove(x)
		q.append((i, a, b, c))
print(len(ans))
print('\n'.join(map(str, ans)))


import sys
read = lambda t=int: list(map(t, sys.stdin.readline().split()))
(N,) = read()
tree = [[] for _ in range(N)]
for _ in range(N - 1):
	(a, b) = read()
	tree[a - 1].append(b - 1)
	tree[b - 1].append(a - 1)
labels = read()
goals = read()
res = []

def dfs(root, par, xor0, xor1, depth):
	if depth == 0:
		if labels[root] ^ xor0 != goals[root]:
			res.append(root)
			xor0 ^= 1
	if depth == 1:
		if labels[root] ^ xor1 != goals[root]:
			res.append(root)
			xor1 ^= 1
	for v in tree[root]:
		if v != par:
			yield (v, root, xor0, xor1, depth ^ 1)
stack = [(0, -1, 0, 0, 0)]
while stack:
	for item in dfs(*stack.pop()):
		stack.append(item)
print(len(res))
for x in res:
	print(x + 1)


import sys
read = lambda t=int: list(map(t, sys.stdin.readline().split()))
(n,) = read()
graph = [[] for _ in range(n)]
for _ in range(n - 1):
	(a, b) = read()
	graph[a - 1].append(b - 1)
	graph[b - 1].append(a - 1)
initial = read()
goal = read()
ansList = []

def dfs(node, par, odd, even, level):
	if level == 0:
		if initial[node] ^ even != goal[node]:
			ansList.append(node)
			even ^= 1
	if level == 1:
		if initial[node] ^ odd != goal[node]:
			ansList.append(node)
			odd ^= 1
	for item in graph[node]:
		if item != par:
			yield (item, node, odd, even, level ^ 1)
stack = [(0, -1, 0, 0, 0)]
while stack:
	for item in dfs(*stack.pop()):
		stack.append(item)
print(len(ansList))
for ele in ansList:
	print(ele + 1)


def DFS(G, i, previous_flip, current_flip):
	global flips, flip_pos
	stack = [(i, previous_flip, current_flip)]
	while len(stack) > 0:
		(i, previous_flip, current_flip) = stack.pop()
		if current_flip == 1:
			inits[i] = 1 - inits[i]
		if inits[i] != goals[i]:
			flips += 1
			flip_pos.append(i)
			current_flip = 1 - current_flip
		for v in G[i]:
			if v != parents[i]:
				parents[v] = i
				stack.append((v, current_flip, previous_flip))
flips = 0
flip_pos = []
n = int(input())
neighbours = [[] for _ in range(n + 1)]
parents = [None] * (n + 1)
for _ in range(n - 1):
	(u, v) = map(int, input().split())
	neighbours[u].append(v)
	neighbours[v].append(u)
inits = [-1] + list(map(int, input().split()))
goals = [-1] + list(map(int, input().split()))
DFS(neighbours, 1, 0, 0)
print(flips)
for x in flip_pos:
	print(x)