SHADES

A map is given on which ~N~ cities are marked, connected by a network of ~M~ one-way roads. Some cities are rural and are marked on the map with white color. Some other cities are urban and are marked on the map with black color. Finally, cities that are neither rural nor urban are marked on the map with gray color.

Rural cities produce food, and urban cities consume it. Consequently, food travels from rural to urban cities along the roads. Cities through which food passes on its route are considered lucky because the economy flourishes there.

Specifically, a city is considered lucky if it is located on a route that starts from a rural city (white), ends in an urban city (black), and does not contain any other urban city except the final one (otherwise, the food would be at risk of being eaten on the way and might not travel until the end of the route). Note that on such a route, both the initial rural city and the final urban city are considered lucky. Also, note that there may be other rural cities between the initial rural city and the final urban city.

You are asked to find which cities are lucky.

Input

The first line of input will contain two integers ~N~ and ~M~, separated by a single space: the number of cities and the number of roads. The second line will contain ~N~ integers separated in pairs by a single space, each of which will be ~0~, ~1~, or ~2~. Each such value corresponds in order to a city. If the value is ~0~, the city is rural (white), if it is ~1~ then the city is urban (black), and if it is ~2~ then it is neither rural nor urban (gray). Each of the next ~M~ lines will contain a pair of numbers ~A~, ~B~, with values between ~1~ and ~N~ inclusive. This pair means that there is a road that goes from city ~A~ to city ~B~. In each road, ~A \neq B~, but there may be more roads between the same cities.

Output

The output should consist of a single line containing exactly ~N~ integers separated in pairs by a single space. Each number corresponds to a city, in order, and will be ~1~ if that city is lucky, otherwise ~0~.

Constraints

~1 \le N, M \le 100.000~.
Execution time limit: 2 sec.
Memory limit: 128 MB.

Example of Input - Output

STDIN (shades.in)

4 5
0 2 1 2
1 2
2 3
3 4
4 1
2 3

STDOUT (shades.out)

1 1 1 0

Explanation

On the path ~1 \rightarrow 2 \rightarrow 3~, the initial city is rural (white) and the final one is urban (black), without any other urban (black) city in between. Therefore, all three of these cities are lucky. There is no path with this property that includes city ~4~, so it is not lucky.