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 dfs(node, adj, vis, val):
  vis[node]=True
  if val[node -1]==1:
    good[node] = True
    return
  for i in adj[node]:
    if not vis[i]:
      dfs(i, adj, vis, val)
      good[node] |= good[i]


if __name__ == '__main__':
  n, m = map(int, input().split())
  val = list(map(int, input().split()))

  vis = [False for i in range(n+1)]
  good = [False for i in range(n+1)]

  adj = [[] for i in range(n+1)]

  for i in range(m):
    x, y = map(int, input().split())
    adj[y].append(x)

  for i in range(n):
    if val[i] == 2:
      dfs(i+1, adj, vis, val)

  for i in range(1,n+1):
    if good[i]:
      print(1)
    else:
      print(0)