Winning Moves in the Tree Game with Special Abilities

Two players, C and K, play a game on a rooted tree with \( n \) nodes. Each node \( i \) initially has \( a_i \) pieces. In each move, a player selects any node \( u \) that has at least one piece and moves one piece from \( u \) to some node \( v \) in \( U(u) \), where

[ U(u)=\text{subtree}(u)\setminus{u} ]

If a player is unable to move (i.e. there is no valid move), they lose. The game is impartial and its outcome is determined by the nim‐sum of the positions.

The Grundy value of a piece located on node \( u \) is defined as the height of \( u \) in the tree (i.e. the maximum distance from \( u \) to any leaf in the subtree with \( u \) as the root, with a leaf having value \( 0 \)). Notice that in any rooted tree with root \( r \) every node \( u \) has a unique height \( g(u) \), and on any path from \( u \) down to a deepest leaf the heights will take all values from \( 0 \) to \( g(u) \). Thus, the move from \( u \) to any node in \( U(u) \) corresponds to a move in Nim with heap size \( g(u) \).

Before the game starts each round, both players are allowed special modifications:

1. In the initial phase, they agree to place an extra piece on node \( x \) and set the tree root to node \( y \). This extra piece is added to the given configuration \( \{a_i\} \) (thus the parity at node \( i \) becomes \( a_i+\delta_{i,x} \) modulo 2).
2. Then, C may decide whether to invoke his special ability. His ability, if used, lets him change the current root from \( y \) to any adjacent node \( R' \) (i.e. any node directly connected to \( y \)). Not using the ability is considered a distinct decision.
3. After C's decision, K may (optionally) use his special ability by placing one extra piece on any chosen node.
4. After these decisions, the game is played with C as the first mover. Once the game ends, the configuration on the tree is restored to the state after step 1.

Let the Grundy value of a node \( j \) (when the tree is rooted at the chosen root \( r \)) be \( g(j) \). The overall nim‐sum of the starting configuration is

[ N = \bigoplus_{j=1}^{n}{\left( g(j) \right)}^{(a_j+\delta_{j,x}) \bmod 2} ]

For a decision by C (choosing a candidate new root \( r \) where \( r=y \) means not using the ability, and \( r \) being an adjacent vertex to \( y \) means using the ability) to guarantee a win regardless of how K uses his ability, the following must hold under the chosen rooting:

• \( N \neq 0 \) (the starting position is a winning position for the first mover).
• For every node \( j \) in the tree, \( N \oplus g(j) \neq 0 \). Since \( N \oplus g(j)=0 \) exactly when \( g(j)=N \), this condition is equivalent to requiring that for all \( j \), \( g(j) \neq N \).

Your task is to determine, for each round, how many decisions (i.e. choices of the new root \( r \) among \( \{ y \} \cup \{\text{neighbors of } y\} \)) yield a configuration that satisfies both conditions above, no matter how K might use his ability.

inputFormat

The first line contains two integers \( n \) and \( m \) -- the number of nodes and the number of rounds, respectively.
The second line contains \( n \) integers \( a_1, a_2, \ldots, a_n \) representing the initial number of pieces on each node.
Each of the next \( n-1 \) lines contains two integers \( u \) and \( v \) indicating an undirected edge between nodes \( u \) and \( v \).
Then follow \( m \) lines; each line contains two integers \( x \) and \( y \) representing the node on which an extra piece is placed and the agreed tree root for that round, respectively.

outputFormat

For each round, output a single integer on a new line indicating the number of decisions available to C that guarantee a winning configuration (as per the conditions described).

sample

3 2
1 0 1
1 2
1 3
2 1
3 1

2
0