## DMOPC '20 Contest 6 P3 - Bread Merchant

View as PDF

Points: 10 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem types

There was once a travelling merchant who traded bread by travelling on routes between cities, with the -th route leading from city to , in only that direction. Unfortunately, one day the merchant was robbed of their fortune of bread money. Furious, the local police decided to give chase and catch the robber.

To avoid getting caught, the robber wants to repeatedly travel along the routes between cities. In fact, as long as they are at a city with at least one outgoing route, they will always travel along one of the outgoing routes to the city it leads to. If they ever reach a city with no outgoing routes, they will be cornered and caught by the police.

Furthermore, some cities have police stations ( if there is a police station in city , and otherwise). In cities with a police station, the police can choose an outgoing route (if one exists) and force the robber to take it. For cities without a police station, the robber can freely choose any route leading from that city. Police stations have no other effects on how the robber is caught.

For each of the cities where the robber could have started from, determine if the police will eventually catch the robber, assuming both the police and robber act optimally.

for all .

for all .

for all .

#### Input Specification

The first line contains integers and .

The next line contains integers .

The next lines each contain integers and . Note that and are not necessarily distinct.

#### Output Specification

On a single line, output space-separated integers, where the -th is the answer if the robber were to start at city . The answer is if the robber will be caught and otherwise.

#### Sample Input

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

#### Sample Output

1 0 0 1 0

#### Explanation

If the robber started at city , then the police can force them to city where they are caught.

If the robber started at either of city or , then they can avoid being caught by always heading to city when they are at city .

If the robber started at city , then they are caught immediately.

If the robber started at city , then the police can only force them to keep taking the route from city back to city itself, and this does not fall under the definition of being caught.