Iahub 对他最近的发现——繁殖树木感到非常自豪。现在,他发明了一种新树,称为异或树。在这一革命性的新发现之后,他发明了一种使用异或树的儿童游戏。
游戏在具有 n 个节点的树上进行,节点编号为 1 到 n。每个节点 i 都有一个初始值 initi,该值不是 0 就是 1。树的根是节点 1。
在游戏过程中,人们可以对树执行多次(可能为零)操作。唯一可用的操作类型是选择节点 x。在有人选择节点 x 后,节点 x 的值翻转,x 的儿子的值保持不变,x 的儿子的儿子的值翻转,x 的儿子的儿子的儿子的值保持不变,依此类推。
游戏的目标是让每个节点 i 都有值 goali,也可以仅为 0 或 1。您需要使用最少的操作次数来达到游戏的目标。
输入
第一行包含一个整数 n (1 ≤ n ≤ 105)。接下来的 n - 1 行中的每一行都包含两个整数 ui 和 vi (1 ≤ ui, vi ≤ n; ui ≠ vi),这意味着节点 ui 和 vi 之间有一条边。
下一行包含n个整数,其中第i个对应于initi(initi为0或1)。下面一行也包含 n 个整数,第 i 个数字对应于 goali(goali 为 0 或 1)。
输出
在第一行输出一个整数cnt,代表您执行的最少操作数。接下来的 cnt 行中的每一行都应包含一个整数 xi,表示您选择一个节点 xi。
示例
输入 #1
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
输出 #1
2 4 7