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.