Overview

We can view each stone as playing an “independent game moving on a DAG” and calculate its Sprague-Grundy value (SG value).
Since the first player, Takahashi, wins if the overall XOR sum (nim-sum) after removing a square is non-zero, we will efficiently determine the nim-sum for each possible square removal.

Analysis

1. Viewing a Single Stone as a Game

When there is a single stone on square \(i\), it can move along the directed edges (arrows).
Since the edges always point from a larger-numbered square to a smaller-numbered square, the graph is a DAG (Directed Acyclic Graph).

In such a game, we can define the SG value \(G_i\) for each square \(i\).

\(G_i\) is the mex (minimum excludant) of the SG values of the squares reachable from square \(i\) in a single move.

\[ G_i = \mathrm{mex}(\{G_v \mid i \to v\}) \]

Here, “mex” refers to the “minimum non-negative integer not contained in the set”.

For example, if the SG values of the reachable squares are \(\{0, 1, 3\}\), the smallest non-negative integer not present is \(2\), so the mex is \(2\).

Since the edges satisfy \(U_j > V_j\), if we process the squares in ascending order of their indices, the SG values of all reachable squares will already have been calculated.

---

2. Case with Multiple Stones

In this game, only one stone is moved in a single turn.
Thus, a state with multiple stones can be considered as the sum of independent games played with each stone.

By the Sprague-Grundy theorem, the overall outcome of the game is determined by the XOR sum of the SG values of all stones.

Let \(X\) be the overall nim-sum:

• If \(X \neq 0\), the first player wins.
• If \(X = 0\), the second player wins.

Square \(i\) contains \(A_i\) stones, each having an SG value of \(G_i\).
Since XORing the same value an even number of times cancels out, only the parity of \(A_i\) matters.

In other words, the initial nim-sum is:

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

If \(A_i\) is even, the contribution of the stones on that square to the overall XOR sum is \(0\).

---

3. Effect of Removal

Before the game starts, Takahashi chooses exactly one square \(i\) and removes all stones on that square.

Let \(X\) be the nim-sum before removal.

When \(A_i\) is even

Originally, the contribution of square \(i\) to the XOR sum was \(0\).
Even if we remove them, the nim-sum does not change.

\[ X' = X \]

When \(A_i\) is odd

Originally, square \(i\) contributed exactly one \(G_i\) to the XOR sum.
Removing it eliminates this contribution, so:

\[ X' = X \oplus G_i \]

The condition for Takahashi to win after the removal is \(X' \neq 0\).

---

4. Case Analysis

Let freq[g] be the number of squares with an odd number of stones whose SG value is \(g\).

Also, let odd_count be the total number of squares with an odd number of stones.

Case 1: Initial Nim-Sum \(X = 0\)

If we remove a square where \(A_i\) is even, the nim-sum remains \(X' = 0\), resulting in a loss.

If we remove a square where \(A_i\) is odd, we get:

\[ X' = 0 \oplus G_i = G_i \]

Therefore, Takahashi can win if and only if he removes a square with \(G_i \neq 0\).

Thus, the answer is:

\[ \text{odd\_count} - \text{freq}[0] \]

---

Case 2: Initial Nim-Sum \(X \neq 0\)

If we remove a square where \(A_i\) is even, the nim-sum remains \(X\), which is non-zero, so Takahashi always wins.

If we remove a square where \(A_i\) is odd, we get:

\[ X' = X \oplus G_i \]

This becomes \(0\) if and only if:

\[ G_i = X \]

Therefore, the only losing moves are removing squares where \(A_i\) is odd and \(G_i = X\).

The answer is:

\[ N - \text{freq}[X] \]

Note that since any SG value is at most \(M\), if \(X > M\), we can treat \(\text{freq}[X]\) as \(0\).
In this case, Takahashi wins regardless of which square is removed, so the answer is \(N\).

---

Why a Naive Approach is Infeasible

If we were to recalculate the outcome of the entire game for each candidate square to be removed, it would take \(O(N^2)\) time or more.
Furthermore, since \(A_i\) can be up to \(10^9\), we cannot process each stone individually.

Instead, we can process the entire problem in \(O(N+M)\) time by:

• Calculating the SG value of each square only once.
• Only considering the parity of the number of stones.
• Maintaining the frequency of each SG value.

Algorithm

1. Record the parity of each \(A_i\).

   • If it is odd, set par[i] = 1.
   • Also count the number of squares with an odd number of stones, odd_count.

2. Store the directed edges (arrows) as an adjacency list.

3. Calculate the SG values sequentially from square \(1\) to \(N\).

   • Since edges always point from a larger index to a smaller index, when processing square \(u\), the SG values of its destinations are already calculated.
   • Treat the SG values of the destinations as a set, and let its mex be sg[u].
   • The SG value of a square with no outgoing edges is \(0\).

4. Calculate the initial nim-sum xorsum by considering only the squares with an odd number of stones.

$\( \text{xorsum} = \bigoplus_{i : A_i \text{ is odd}} sg[i] \)$

At the same time, count freq[sg[i]].

1. Find the answer based on the value of xorsum.

   • If xorsum == 0:

   $\( \text{ans} = \text{odd\_count} - \text{freq}[0] \)$

   • If xorsum != 0:
     • If xorsum <= M:

   $\( \text{ans} = N - \text{freq}[\text{xorsum}] \)$

   • If xorsum > M:

   $\( \text{ans} = N \)$

Complexity

• Time Complexity: \(O(N+M)\)
• Space Complexity: \(O(N+M)\)

In the calculation of SG values, each edge is visited exactly once.
Since computing the mex also takes time proportional to the out-degree of each vertex, the overall time complexity is \(O(N+M)\).

Key Implementation Points

• Since \(N\) can be as large as \(10^6\), fast I/O is used.

• Instead of storing the exact values of \(A_i\), only their parities are stored in a bytearray.

• Initializing an array for each mex calculation would be too slow. Therefore, a seen array and a stamp variable are used to keep track of the “SG values visited in the current step”.

• While each individual SG value is at most \(M\), the xorsum (which is the XOR sum of multiple SG values) can exceed \(M\). Therefore, we handle the case xorsum > M separately.

  Source Code

import sys

def main():
    data = sys.stdin.buffer.read() + b' '
    idx = 0

    def ni():
        nonlocal idx
        while data[idx] <= 32:
            idx += 1
        x = 0
        while data[idx] > 32:
            x = x * 10 + (data[idx] - 48)
            idx += 1
        return x

    N = ni()
    M = ni()

    par = bytearray(N + 1)
    odd_count = 0
    for i in range(1, N + 1):
        if ni() & 1:
            par[i] = 1
            odd_count += 1

    head = [-1] * (N + 1)
    to = [0] * M
    nxt = [0] * M

    for e in range(M):
        u = ni()
        v = ni()
        to[e] = v
        nxt[e] = head[u]
        head[u] = e

    data = None

    sg = [0] * (N + 1)
    seen = [0] * (M + 1)
    stamp = 0

    for u in range(1, N + 1):
        e = head[u]
        if e != -1:
            stamp += 1
            while e != -1:
                seen[sg[to[e]]] = stamp
                e = nxt[e]

            g = 0
            while seen[g] == stamp:
                g += 1
            sg[u] = g

    freq = [0] * (M + 1)
    xorsum = 0

    for i in range(1, N + 1):
        if par[i]:
            g = sg[i]
            xorsum ^= g
            freq[g] += 1

    if xorsum == 0:
        ans = odd_count - freq[0]
    elif xorsum <= M:
        ans = N - freq[xorsum]
    else:
        ans = N

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.5-high.