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
from collections import defaultdict

class Graph: 
    def __init__(self): 
        self.graph = defaultdict(list) 
        self.values = defaultdict()
        self.interesting = defaultdict()

    def addEdge(self,u,v): 
        # directed graph
        self.graph[u].append(v)  
  
    def DFSUtil(self, v, visited): 
        
        visited[v-1] = True
        # visiting its adj nodes
        for i in self.graph[v]:
            if visited[i-1] is False and  self.values[i] != 1: 
                res = self.DFSUtil(i, visited)
                if res is True:
                    self.interesting[v] = 1

        if self.values[v] == 2 or self.interesting[v] == 1:
            self.interesting[v] = 1
            return True
        else:
            return False

    def DFS(self,n,s):

        visited =[False]*n
        res = self.DFSUtil(s, visited) 
        return self.interesting

    def assignStates(self, values):
        
        for i,item in enumerate(values):
            self.values[i+1] = item 
            self.interesting[i+1] = 0 


g = Graph() 

n, m = input().split()
n = int(n)
m = int(m)

f = input().split()
f = [int(i) for i in f]
g.assignStates(f)

start = []
for _ in range(m):
    x, y = input().split()
    x = int(x)
    y = int(y)
    if f[x-1] == 1:
        start.append(int(x))
    if f[y-1] == 1:
        start.append(int(y))

    g.addEdge(x, y)


start = list(dict.fromkeys(start))

for k in start:
    theres = g.DFS(n, k)

for a in theres.values():
    print(a)






