Life is not easy for the perfectly common variable named Vasya. Wherever it goes, it is either assigned a value, or simply ignored, or is being used!

Vasya's life goes in states of a program. In each state, Vasya can either be used (for example, to calculate the value of another variable), or be assigned a value, or ignored. Between some states are directed (oriented) transitions.

A path is a sequence of states v₁, v₂, ..., v_x, where for any 1 ≤ i < x exists a transition from v_i to v_i + 1.

Vasya's value in state v is interesting to the world, if exists path p₁, p₂, ..., p_k such, that p_i = v for some i (1 ≤ i ≤ k), in state p₁ Vasya gets assigned a value, in state p_k Vasya is used and there is no state p_i (except for p₁) where Vasya gets assigned a value.

Help Vasya, find the states in which Vasya's value is interesting to the world.

The first line contains two space-separated integers n and m (1 ≤ n, m ≤ 10⁵) — the numbers of states and transitions, correspondingly.

The second line contains space-separated n integers f₁, f₂, ..., f_n (0 ≤ f_i ≤ 2), f_i described actions performed upon Vasya in state i: 0 represents ignoring, 1 — assigning a value, 2 — using.

Next m lines contain space-separated pairs of integers a_i, b_i (1 ≤ a_i, b_i ≤ n, a_i ≠ b_i), each pair represents the transition from the state number a_i to the state number b_i. Between two states can be any number of transitions.

Print n integers r₁, r₂, ..., r_n, separated by spaces or new lines. Number r_i should equal 1, if Vasya's value in state i is interesting to the world and otherwise, it should equal 0. The states are numbered from 1 to n in the order, in which they are described in the input.