A8387 | Variable, or There and Back Again

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_{1},v_{2},...,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_{1},p_{2},...,p_{k}$ such, that $p_{i}=v$ for some $i$ $(1<=i<=k)$ , in state $p_{1}$ Vasya gets assigned a value, in state $p_{k}$ Vasya is used and there is no state $p_{i}$ (except for $p_{1}$ ) 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^{5}$ ) — the numbers of states and transitions, correspondingly.

The second line contains space-separated $n$ integers $f_{1},f_{2},...,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_{1},r_{2},...,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.