Overview

This problem is a two-player game where stones are moved on a DAG (Directed Acyclic Graph). Since each stone can be moved independently, we can solve it efficiently by applying the concepts of “Nim” and “Grundy values” (Sprague-Grundy theorem) from game theory.

---

Analysis

1. Decomposing the game into independent “stones”

In this game, a player chooses one stone and moves it along an arrow. The movement of each stone has absolutely no effect on the movement of other stones. A game composed of multiple independent games progressing in parallel is called a “sum of games (multi-pile Nim)”.

Due to this property, the Sprague-Grundy theorem holds: “The winning/losing state of the entire board is determined by the XOR sum (exclusive OR) of the Grundy values of the vertices where the stones are located.”

2. Definition of the Grundy value \(G[i]\) of vertex \(i\)

The Grundy value \(G[i]\) of a game where a single stone is at vertex \(i\) is recursively defined as follows:

\[G[i] = \text{mex}(\{ G[v] \mid \text{there is an arrow from vertex } i \text{ to vertex } v \})\]

Here, \(\text{mex}(S)\) denotes the minimum non-negative integer (\(0, 1, 2, \ldots\)) not contained in the set \(S\). Since arrows always point from vertices with larger indices to vertices with smaller indices (\(U_j > V_j\)), this graph is a DAG, and we can determine \(G[i]\) sequentially starting from vertex \(1\).

3. Multiple stones on the same vertex

When there are \(A_i\) stones on vertex \(i\), they can be considered as “\(A_i\) independent games, each with a Grundy value of \(G[i]\)”. The XOR sum of the same value is \(0\) if there is an even number of them, and the value itself if there is an odd number of them.

• If \(A_i\) is even: \(G[i] \oplus G[i] \oplus \dots \oplus G[i] = 0\)
• If \(A_i\) is odd: \(G[i] \oplus G[i] \oplus \dots \oplus G[i] = G[i]\)

Therefore, the XOR sum \(X\) of the initial state of the entire game is the “XOR sum of \(G[i]\) for all vertices \(i\) where the number of stones \(A_i\) is odd.”

\[X = \bigoplus_{A_i \text{ is odd}} G[i]\]

4. Impact of Takahashi’s “removal” operation

Before the game starts, Takahashi chooses an arbitrary vertex \(k\) and removes all stones from that vertex (setting \(A_k\) to \(0\), which is an even number). Let \(X'_k\) be the XOR sum of the entire game after performing this “removal”. It can be expressed as follows:

• If \(A_k\) was originally odd: Since the contribution \(G[k]\) of vertex \(k\) disappears, the XOR sum after removal becomes \(X'_k = X \oplus G[k]\).
• If \(A_k\) was originally even: Since it did not contribute to the overall XOR sum \(X\) in the first place, the XOR sum after removal remains \(X'_k = X\).

5. Winning / Losing Condition

The condition for the first player (Takahashi) to win under optimal play is that “the XOR sum at the start of the game (immediately after the removal) is non-zero.” Therefore, by counting the number of \(k \in \{1, \dots, N\}\) such that \(X'_k \neq 0\), we get the desired answer.

---

Algorithm

1. Calculating Grundy Values: For each vertex \(i\) from \(1\) to \(N\) in order, we compute \(G[i]\) by finding the \(\text{mex}\) of the Grundy values of the vertices reachable from \(i\). Here, due to the problem constraint (\(U_j > V_j\)), all reachable vertices are guaranteed to have their Grundy values already calculated (no topological sort is required).

2. Calculating the Overall XOR Sum: Calculate the XOR sum \(X\) of \(G[i]\) for all \(i\) where \(A_i\) is odd.

3. Simulating the Removal: For each vertex \(k\), calculate the XOR sum \(X'_k\) after removal.

   • If \(A_k \pmod 2 == 1\), then \(X'_k = X \oplus G[k]\)
   • If \(A_k \pmod 2 == 0\), then \(X'_k = X\)

Count the number of \(k\) such that \(X'_k \neq 0\) and output it.

---

Complexity

• Time Complexity: \(O(N + M)\)
  • In the calculation of Grundy values, we traverse each vertex and each edge, which can be processed in \(O(N + M)\) time overall.
  • Since the determination of the XOR sum after removal for each \(k\) can be done in \(O(1)\) time, the decision part takes \(O(N)\) time.
• Space Complexity: \(O(N + M)\)
  • It takes \(O(N + M)\) memory to store the adjacency list adj of the graph, and \(O(N)\) memory for the array G storing the Grundy values and the marked array.

---

Implementation Points

• Fast Calculation of \(\text{mex}\): When finding the \(\text{mex}\) for each vertex \(i\), initializing the marking array (marked) with false every time would take \(O(N^2)\) time in the worst case. To prevent this, we do “mark reachable vertices” \(\to\) “find \(\text{mex}\)” \(\to\) “unmark reachable vertices”. This allows the initialization of the marking array to be done in \(O(\text{out-degree})\) time, achieving \(O(N + M)\) overall.

  Source Code

#include <iostream>
#include <vector>

using namespace std;

int main() {
    // Optimize standard I/O operations for speed
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M;
    if (!(cin >> N >> M)) return 0;

    vector<long long> A(N + 1);
    for (int i = 1; i <= N; ++i) {
        cin >> A[i];
    }

    vector<vector<int>> adj(N + 1);
    for (int i = 0; i < M; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
    }

    vector<int> G(N + 1, 0);
    vector<bool> marked(N + 2, false);

    // Compute Grundy values in O(N + M) time
    for (int i = 1; i <= N; ++i) {
        for (int v : adj[i]) {
            int g = G[v];
            if (g < (int)marked.size()) {
                marked[g] = true;
            }
        }
        int mex = 0;
        while (marked[mex]) {
            mex++;
        }
        G[i] = mex;
        // Clean up the marked array for the next vertices
        for (int v : adj[i]) {
            int g = G[v];
            if (g < (int)marked.size()) {
                marked[g] = false;
            }
        }
    }

    // Calculate the initial XOR-sum of the game
    int X = 0;
    for (int i = 1; i <= N; ++i) {
        if (A[i] % 2 == 1) {
            X ^= G[i];
        }
    }

    // Count the number of valid choices for removal
    int ans = 0;
    for (int k = 1; k <= N; ++k) {
        int X_prime = X;
        if (A[k] % 2 == 1) {
            X_prime ^= G[k];
        }
        if (X_prime != 0) {
            ans++;
        }
    }

    cout << ans << "\n";

    return 0;
}

---

This editorial was generated by gemini-3.5-flash-high.