← 返回题目列表

Codeforces · 164/A

A. 变量,或来来回回

中文机器翻译题面 查看原题

对于名为 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 的价值永远不会让世界感兴趣。