Overview

This problem asks us to determine the outcome of a two-player game (an impartial game) played on a Directed Acyclic Graph (DAG). By using the concept of Grundy values (or Nim-values) from game theory, we can reduce the state of the game to the classic game of “Nim” to solve it.

We want to find the number of squares such that if Takahashi performs the stone removal operation “exactly once” on that square before the game starts, the subsequent game becomes a winning state for the first player (Takahashi).

---

Analysis

1. Game Rules and Reduction to “Grundy Values”

This game is an “impartial game” where players take turns making moves under the same rules. Also, since arrows always point from squares with larger numbers to squares with smaller numbers, the graph is a DAG (Directed Acyclic Graph) with no cycles.

Such a game can be treated as the famous game “Nim” by calculating the Grundy value (\(G\)) of each square.

Definition of Grundy Value

The Grundy value \(G[i]\) for each square \(i\) is defined as follows: * If there are no arrows starting from square \(i\): \(G[i] = 0\) * Otherwise: The minimum non-negative integer (\(\text{mex}\)) that is not contained in the set of Grundy values of the squares directly reachable by following an arrow from square \(i\). $\(G[i] = \text{mex}(\{G[v] \mid \text{there exists an arrow } i \to v\})\)$

For example, if you can move from square \(i\) to squares with \(G[v] = 0, 1, 3\), the minimum non-negative integer not in the set \(\{0, 1, 3\}\) is \(2\), so \(G[i] = 2\).

2. Nim-Sum of the Entire Game

Each square \(i\) has \(A_i\) stones. This is equivalent to having \(A_i\) Nim piles, each of value \(G[i]\). In Nim, the exclusive OR (XOR sum) of the states of multiple piles is called the Nim-Sum, which determines the outcome of the game.

Let’s consider XORing the same value \(G[i]\) a total of \(A_i\) times: * When \(A_i\) is even: \(G[i] \oplus G[i] \oplus \dots \oplus G[i] = 0\) * When \(A_i\) is odd: \(G[i] \oplus G[i] \oplus \dots \oplus G[i] = G[i]\)

Therefore, if the Nim-Sum of the entire game at the start is \(S\), then \(S\) is the XOR sum of \(G[i]\) for all squares \(i\) where the number of stones \(A_i\) is odd. $\(S = \bigoplus_{A_i \text{ is odd}} G[i]\)$

According to the standard Nim theorem, “if the Nim-Sum is non-zero when it is your turn, the first player wins; if it is \(0\), the second player wins.”

3. Effect of the “Removal” Operation

Before the game begins, Takahashi can choose any single square \(i\) and remove all stones from that square (setting \(A_i\) to \(0\)). How does this operation change the overall Nim-Sum \(S\)?

• If we choose a square \(i\) where \(A_i\) is even: Since \(G[i]\) was not originally involved in the calculation of \(S\) (because an even number of XORs resulted in \(0\)), setting the number of stones to \(0\) (which is still even) leaves the overall Nim-Sum unchanged as \(S\).
• If we choose a square \(i\) where \(A_i\) is odd: Originally, \(G[i]\) was included once in the calculation of \(S\). Since this becomes \(0\) (even), the overall Nim-Sum changes to \(S \oplus G[i]\).

4. Conditions for Takahashi’s Victory

The game begins after Takahashi performs the removal. Since it is Takahashi’s turn (first player) at this point, the condition for Takahashi to win is “the Nim-Sum after removal is non-zero”.

We can count the number of “squares that must not be chosen” (which result in a Nim-Sum of \(0\) after removal, meaning Takahashi loses) and subtract this from the total number of squares \(N\) to find the answer.

Case 1: When the initial Nim-Sum \(S = 0\)

• If we choose a square \(i\) with an even \(A_i\), the Nim-Sum after removal remains \(S = 0\), resulting in a loss.
• If we choose a square \(i\) with an odd \(A_i\), the Nim-Sum after removal becomes \(S \oplus G[i] = 0 \oplus G[i] = G[i]\).
  • This becomes \(0\) if \(G[i] = 0\) (loss).
  • This becomes non-zero if \(G[i] \neq 0\) (win).

Therefore, the winning squares are “squares where \(A_i\) is odd and \(G[i] \neq 0\)”.

Case 2: When the initial Nim-Sum \(S \neq 0\)

• If we choose a square \(i\) with an even \(A_i\), the Nim-Sum after removal remains \(S \neq 0\), resulting in a win.
• If we choose a square \(i\) with an odd \(A_i\), the Nim-Sum after removal becomes \(S \oplus G[i]\).
  • This becomes \(0\) (loss) if and only if \(S \oplus G[i] = 0\), which means \(G[i] = S\).

Therefore, the only losing squares are “squares where \(A_i\) is odd and \(G[i] = S\)”. The number of winning squares is the total minus these: \(N - (\text{number of squares satisfying the condition})\).

---

Algorithm

1. Construct the Adjacency List: Build the graph from the given arrows (directed edges).
2. Calculate Grundy Values: Iterate through the vertices in order from \(1\) to \(N\) to determine the Grundy value \(G[u]\) for each square.
   • Due to the constraint \(U_j > V_j\), processing the squares in ascending order of their indices guarantees that the Grundy values of the destination squares have already been calculated (dynamic programming in topological order).
   • The \(\text{mex}\) calculation is done efficiently by marking the \(G[v]\) of the destination squares.
3. Calculate the Initial Nim-Sum \(S\): Find the XOR sum \(S\) of \(G[i]\) for all squares where \(A_i\) is odd.
4. Count Winning Squares:
   • If \(S = 0\): Count the number of squares where \(A_i\) is odd and \(G[i] \neq 0\).
   • If \(S \neq 0\): Count the number of squares where \(A_i\) is odd and \(G[i] = S\), then subtract this from \(N\).

---

Complexity

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

  • In determining the Grundy values, each vertex and each edge is explored a constant number of times, taking \(O(N + M)\) to traverse the graph.
  • The subsequent aggregation process takes \(O(N)\).
  • Overall, this runs fast enough for the constraints \(N \le 10^6, M \le 10^5\).

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

  • We use \(O(N + M)\) memory for the graph’s adjacency list, and \(O(N)\) for arrays to store the Grundy values and the number of stones.

---

Implementation Details

• Optimizing the \(\text{mex}\) calculation: When finding \(\text{mex}\) for each vertex \(u\), clearing the visited array every time would lead to a worst-case time complexity of \(O(N \times (\text{maximum degree}))\), which may cause TLE (Time Limit Exceeded). To prevent this, we can record “which vertex’s process visited this value” using visited[g] = u, thereby avoiding the need to re-initialize the array.

• Omitting Topological Sort: In a general DAG, a topological sort is required. However, in this problem, because of the constraint “arrows always point from squares with larger numbers to squares with smaller numbers,” we can correctly calculate the Grundy values bottom-up simply by looping from \(1\) to \(N\) in ascending order.

  Source Code

import sys

def solve():
    # 入力を高速に読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    M = int(input_data[1])
    
    # A_1 から A_N (1-indexed)
    A = [0] * (N + 1)
    for i in range(1, N + 1):
        A[i] = int(input_data[1 + i])
        
    # 隣接リストの構築
    adj = [[] for _ in range(N + 1)]
    idx = 1 + N + 1
    for _ in range(M):
        u = int(input_data[idx])
        v = int(input_data[idx+1])
        adj[u].append(v)
        idx += 2
        
    # 各マスのグランディ値(G)の計算
    G = [0] * (N + 1)
    visited = [0] * (M + 2)
    
    for u in range(1, N + 1):
        if not adj[u]:
            G[u] = 0
            continue
        for v in adj[u]:
            g = G[v]
            if g < M + 2:
                visited[g] = u
        mex = 0
        while visited[mex] == u:
            mex += 1
        G[u] = mex
        
    # 初期状態のグランディ値(S)の計算
    S = 0
    for i in range(1, N + 1):
        if A[i] & 1:
            S ^= G[i]
            
    # 高橋君が勝てる除去の対象マスの個数を計算
    if S == 0:
        ans = 0
        for i in range(1, N + 1):
            if (A[i] & 1) and G[i] != 0:
                ans += 1
    else:
        invalid = 0
        for i in range(1, N + 1):
            if (A[i] & 1) and G[i] == S:
                invalid += 1
        ans = N - invalid
        
    print(ans)

if __name__ == '__main__':
    solve()

---

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