E. 黑白树

时间限制：4 秒
内存限制：512 MB

给你一棵由 $n$ 个顶点组成的树。其中一些顶点（至少两个）是黑色的，其余所有顶点是白色的。

你将一枚棋子放在树的一个顶点上，然后执行以下操作：

设棋子当前所在的顶点为 $x$。你选择一个黑色顶点 $y$，然后将棋子沿着从 $x$ 到 $y$ 的简单路径上的第一条边移动。
你不允许在连续两次操作中选择相同的黑色顶点 $y$（即，对于每两个连续的操作，所选的黑色顶点必须不同）。

当棋子移动到黑色顶点时（如果它一开始就放在黑色顶点上，则不执行任何操作），或者当执行的操作次数超过 $100500$ 时，你就结束操作。

对于每个顶点 $i$，你需要判断是否存在一个（可能为空的）操作序列，使得棋子从初始顶点 $i$ 出发最终能移动到某个黑色顶点。

输入格式

第一行包含一个整数 $n$（$3 \le n \le 3 \cdot 10^5$）—— 树的顶点数。

第二行包含 $n$ 个整数 $c_1, c_2, \dots, c_n$（$0 \le c_i \le 1$），其中 $c_i = 0$ 表示第 $i$ 个顶点是白色，$c_i = 1$ 表示第 $i$ 个顶点是黑色。至少有两个 $c_i$ 等于 $1$。

接下来的 $n-1$ 行，每行包含两个整数 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le n$；$u_i \ne v_i$）—— 某条边的两个端点。这些边构成一棵树。

输出格式

输出 $n$ 个整数。第 $i$ 个整数应为 $1$，如果存在一个（可能为空的）操作序列使得棋子从顶点 $i$ 出发能移动到某个黑色顶点；否则输出 $0$。

示例

输入

8
0 1 0 0 0 0 1 0
8 6
2 5
7 8
6 5
4 5
6 1
7 3

输出

0 1 1 1 1 0 1 1