对于名为 Vasya 的完全常见变量来说,生活并不容易。无论它走到哪里,它要么被分配一个值,要么被简单地忽略,要么正在被使用!
Vasya 的生活按照程序进行。在每种状态下,Vasya 都可以被使用(例如,计算另一个变量的值),或者被分配一个值,或者被忽略。某些状态之间是定向(定向)转换。
路径是状态 v1、v2、...、vx 的序列,其中对于任意 1 ≤ i < x,存在从 vi 到 vi + 1 的转换。
Vasya 在状态 v 中的值对世界来说很有趣,如果存在路径 p1, p2, ..., pk 这样,对于某些 i (1 ≤ i ≤ k),pi = v,在状态 p1 Vasya 被分配一个值,在状态 pk Vasya 被使用,并且没有状态 pi(除了 p1)其中 Vasya 被分配一个值。
帮助 Vasya,找到 Vasya 的价值令世界感兴趣的状态。
输入
第一行包含两个空格分隔的整数 n 和 m (1 ≤ n, m ≤ 105) — 相应地,状态和转换的数量。
第二行包含空格分隔的 n 个整数 f1, f2, ..., fn (0 ≤ fi ≤ 2),fi 描述了在状态 i 下对 Vasya 执行的操作:0 表示忽略,1 — 赋值,2 — 使用。
接下来 m 行包含空格分隔的整数对 ai, bi (1 ≤ ai, bi ≤ n, ai ≠ bi),每对表示从状态号 ai 到状态号 bi 的转换。两个状态之间可以有任意数量的转换。
输出
打印 n 个整数 r1, r2, ..., rn,用空格或换行符分隔。如果 Vasya 在状态 i 中的值对世界感兴趣,则数字 ri 应等于 1,否则应等于 0。状态按输入中描述的顺序从 1 到 n 编号。
示例
输入 #1
4 3 1 0 0 2 1 2 2 3 3 4
输出 #1
1 1 1 1
输入 #2
3 1 1 0 2 1 3
输出 #2
1 0 1
输入 #3
3 1 2 0 1 1 3
输出 #3
0 0 0
注意
在第一个示例中,程序声明可用于创建使 Vasya 的价值引起全世界关注的唯一路径,1 $$\rightarrow$$ 2 $$\rightarrow$$ 3 $$\rightarrow$$ 4;它包括所有国家,因此瓦夏在所有国家中的价值都引起了世界的兴趣。
第二个样本使 Vasya 的价值引起世界关注的唯一路径是 , — 1 $$\rightarrow$$ 3;状态 2 不包括在那里。
在第三个样本中,我们无法从各州得出任何让世界对 Vasya 的价值感兴趣的路径,因此 Vasya 的价值永远不会让世界感兴趣。