この問題は、不偏ゲームと Grundy 数の知識を使うことで解くことができます。

不偏ゲームと Grundy 数については、AWC0067 E の解説などを参照してください。

この問題では、プレイヤーはそれぞれの手番でただひとつの石を選び、その石に対して（他の石に依存しない）操作を行います。

これは単一の石からなるゲームの合併だと考えることができるので、単一の石からなるゲームの Grundy 数を求めることができれば、それぞれの石についての Grundy 数の総 xor を求めることでゲーム全体の Grundy 数を求めることができます。

この問題で与えられるグラフは DAG （有向非巡回グラフ）なので、次の事実をもとに頂点番号が小さいほうから Grundy 数を求めていくことができます。

不偏ゲーム \(G\) について、\(G\) から \(1\) 手進めた状態としてありえるゲームの集合を \(\lbrace G _ 1,G _ 2,\ldots\rbrace\) としたとき、次の等式が成り立つ。\[\mathcal G(G)=\operatorname{mex}\lbrace\mathcal G(G _ 1),\mathcal G(G _ 2),\ldots\rbrace\] ただし、整数の集合 \(S\) に対する \(\operatorname{mex} S\) は \(S\) に含まれない最小の非負整数を表す。

それぞれの頂点について、その頂点のみにひとつの石があり、それ以外の頂点に石が存在しないようなゲームの Grundy 数を求めたとし、頂点 \(i\) に対するその値を \(G _ i\) とします。

高橋君が除去を行う前のゲームの Grundy 数は次のようになります（ここで、\(a\oplus b\) で \(a\) と \(b\) のビットごとの排他的論理和を、\(\displaystyle\bigoplus _ {i=1} ^ Nx _ i\) で \(x _ 1\oplus x _ 2\oplus\cdots\oplus x _ N\) を表します）。\[G=\bigoplus _ {i=1} ^ NG _ i\times(A _ i\,\%\,2)\] 頂点 \(i\) に対して除去を行うと、ゲームの Grundy 数は \(G\oplus(G _ i\times(A _ i\,\%\,2))\) になります。 先手の高橋君がゲームに勝つためには、これが \(0\) でないようにする必要があります。 \(x\oplus y\ne0\iff x\ne y\) なので、\(G\) を求めたあと \(G\ne G _ i\times(A _ i\,\%\,2)\) となるような \(i\) の個数を求めることで、この問題を解くことができました。

時間計算量は \(G _ i\) を求める部分がボトルネックとなり \(O(N+M\log N)\) などになります。

実装例は以下のようになります。

#include <iostream>
#include <vector>
#include <set>
using namespace std;

int main() {
    int N, M;
    cin >> N >> M;
    vector<int> A(N);
    for (int& a : A) {
        cin >> a;
        a %= 2; // A の偶奇だけが結果に関係する
    }

    // to[i] := i から辺が伸びる頂点のリスト
    vector<vector<int>> to(N);
    for (int i = 0; i < M; ++i) {
        int u, v;
        cin >> u >> v;
        --u; // 0-indexed にしておく
        --v;
        to[u].emplace_back(v);
    }

    // Grundy 数を求める
    vector<int> grundy(N);
    for (int i = 0; i < N; ++i) {
        set<int> next_grundy; // 行先の値を列挙して
        for (int next : to[i]) {
            next_grundy.emplace(grundy[next]);
        }
        int g = 0;
        while (next_grundy.contains(g)) {
            ++g;
        } // 含まれない最小値が答え
        grundy[i] = g;
    }

    // 除去を行わなかったときの Grundy 数を求めて
    int G = 0;
    for (int i = 0; i < N; ++i) {
        G ^= grundy[i] * A[i];
    }

    // それと等しくないところを数える
    int ans = 0;
    for (int i = 0; i < N; ++i) {
        if (G != grundy[i] * A[i]) {
            ++ans;
        }
    }
    cout << ans << endl;
    return 0;
}

N, M = map(int, input().split())

# A の偶奇だけが結果に関係する
A = [a % 2 for a in map(int, input().split())]

# to[i] := i から辺が伸びる頂点のリスト
to = [[] for i in range(N)]
for i in range(M):
    u, v = map(int, input().split())
    u -= 1 # 0-indexed にしておく
    v -= 1
    to[u].append(v)

# Grundy 数を求める
grundy = [0 for i in range(N)]
for i in range(N):
    next_grundy = set() # 行先の値を列挙して
    for next in to[i]:
        next_grundy.add(grundy[next])
    g = 0
    while g in next_grundy:
        g += 1
    # 含まれない最小値が答え
    grundy[i] = g

# 除去を行わなかったときの Grundy 数を求めて
G = 0
for g, a in zip(grundy, A):
    G ^= g * a

# それと等しくないところを数える
ans = 0
for g, a in zip(grundy, A):
    if G != g * a:
        ans += 1

print(ans)