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*<sub class="lower-index">1</sub>, *v*<sub class="lower-index">2</sub>, ..., *v*<sub class="lower-index">*x*</sub>, where for any 1 ≤ *i* &lt; *x* exists a transition from *v*<sub class="lower-index">*i*</sub> to *v*<sub class="lower-index">*i* + 1</sub>.

Vasya's value in state *v* is interesting to the world, if exists path *p*<sub class="lower-index">1</sub>, *p*<sub class="lower-index">2</sub>, ..., *p*<sub class="lower-index">*k*</sub> such, that *p*<sub class="lower-index">*i*</sub> = *v* for some *i* (1 ≤ *i* ≤ *k*), in state *p*<sub class="lower-index">1</sub> Vasya gets assigned a value, in state *p*<sub class="lower-index">*k*</sub> Vasya is used and there is no state *p*<sub class="lower-index">*i*</sub> (except for *p*<sub class="lower-index">1</sub>) 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<sup class="upper-index">5</sup>) — the numbers of states and transitions, correspondingly.

The second line contains space-separated *n* integers *f*<sub class="lower-index">1</sub>, *f*<sub class="lower-index">2</sub>, ..., *f*<sub class="lower-index">*n*</sub> (0 ≤ *f*<sub class="lower-index">*i*</sub> ≤ 2), *f*<sub class="lower-index">*i*</sub> 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*<sub class="lower-index">*i*</sub>, *b*<sub class="lower-index">*i*</sub> (1 ≤ *a*<sub class="lower-index">*i*</sub>, *b*<sub class="lower-index">*i*</sub> ≤ *n*, *a*<sub class="lower-index">*i*</sub> ≠ *b*<sub class="lower-index">*i*</sub>), each pair represents the transition from the state number *a*<sub class="lower-index">*i*</sub> to the state number *b*<sub class="lower-index">*i*</sub>. Between two states can be any number of transitions.
4 3
1 0 0 2
1 2
2 3
3 4
1
1
1
1
3 1
1 0 2
1 3
1
0
1
3 1
2 0 1
1 3
0
0
0
4 4
1 0 2 0
1 2
2 3
3 4
4 1
1
1
1
0
2 1
2 1
2 1
1
1
3 2
1 2 0
1 2
3 2
1
1
0
8 8
1 0 0 2 1 0 0 2
1 2
2 3
3 2
2 4
6 8
7 6
6 7
5 6
1
1
1
1
1
1
1
1
6 6
1 0 0 0 0 2
1 2
2 3
3 4
4 5
5 2
3 6
1
1
1
1
1
1
def d1(g,used,ans,v):
    used[v] = True
    ans[v] += 1
    for i in range(len(g[v])):
        to = g[v][i]
        if to == 1 and used[i] == 0:
            d1(g,used,ans,i)

def d2(g,used,ans,v):
    used[v] = 1
    ans[v] += 1
    for i in range(len(g[v])):
        to = g[v][i]
        if to == -1 and used[i] == 0:
            d2(g,used,ans,i)

n, m = map(int,input().split())
f = list(map(int,input().split()))
g = []
for i in range(n):
    g.append([0] * n)
for i in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    g[a][b] = 1
    g[b][a] = -1

ans = [0] * n
used = [0] * n
for i in range(n):
    if used[i] == 0 and f[i] == 1:
        d1(g,used,ans,i)
used = [0] * n
for i in range(n):
    if used[i] == 0 and f[i] == 2:
        d2(g,used,ans,i)
for i in range(n):
    if ans[i] == 2:
        print(1)
    else:
        print(0)

