Variable, or There and Back Again

题目连接：

http://codeforces.com/problemset/problem/164/A

Description

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 v1, v2, ..., vx, where for any 1 ≤ i < x exists a transition from vi to vi + 1.

Vasya's value in state v is interesting to the world, if exists path p1, p2, ..., pk such, that pi = v for some i(1 ≤ i ≤ k), in state p1 Vasya gets assigned a value, in state pk Vasya is used and there is no state pi (except for p1) where Vasya gets assigned a value.

Help Vasya, find the states in which Vasya's value is interesting to the world.

Input

The first line contains two space-separated integers n and m (1 ≤ n, m ≤ 105) — the numbers of states and transitions, correspondingly.

The second line contains space-separated n integers f1, f2, ..., fn (0 ≤ fi ≤ 2), fi 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 ai, bi (1 ≤ ai, bi ≤ n, ai ≠ bi), each pair represents the transition from the state number ai to the state number bi. Between two states can be any number of transitions.

Output

Print n integers r1, r2, ..., rn, separated by spaces or new lines. Number ri should equal 1, if Vasya's value in state i is interesting to the world and otherwise, it should equal 0. The states are numbered from 1 to n in the order, in which they are described in the input.

Sample Input

4 3

1 0 0 2

1 2

2 3

3 4

Sample Output

1

1

1

1

Hint

题意

给你n和m，表示有n个状态和m条单向边

快乐路径表示从1开始，2结束的路径，这个路径中间没有1就可以

问你这些状态哪些是快乐路径上的，哪些不是

题解：

两次bfs/dfs就好呢

第一次从1开始搜，第2次2开始搜

如果这个点在两次搜索的时候，都经过的话，就是快乐路径上的

否则就不是

代码

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e6+6;

vector<int> E1[maxn];

vector<int> E2[maxn];

int vis1[maxn];

int vis2[maxn];

int a[maxn];

queue<int> Q;

int main()

{

    int n,m;

    scanf("%d%d",&n,&m);

    for(int i=1;i<=n;i++)

        scanf("%d",&a[i]);

    for(int i=1;i<=m;i++)

    {

        int x,y;

        scanf("%d%d",&x,&y);

        E1[x].push_back(y);

        E2[y].push_back(x);

    }

    for(int i=1;i<=n;i++)

        if(a[i]==1)

        {

            vis1[i]=1;

            Q.push(i);

        }

    while(!Q.empty())

    {

        int now = Q.front();

        Q.pop();

        for(int i=0;i<E1[now].size();i++)

        {

            int x = E1[now][i];

            if(a[x]==1)continue;

            if(vis1[x])continue;

            vis1[x]=1;

            Q.push(x);

        }

    }

    while(!Q.empty())Q.pop();

    for(int i=1;i<=n;i++)

        if(a[i]==2)

        {

            vis2[i]=1;

            Q.push(i);

        }

    while(!Q.empty())

    {

        int now = Q.front();

        Q.pop();

        for(int i=0;i<E2[now].size();i++)

        {

            int x = E2[now][i];

            if(a[x]==1)

                vis2[x]=1;

            if(vis2[x])continue;

            vis2[x]=1;

            Q.push(x);

        }

    }

    for(int i=1;i<=n;i++)

        if(vis1[i]&&vis2[i])

            printf("1\n");

        else

            printf("0\n");

}