Chain XOR Strategies

Aiden is attempting to hack the dedsec system to seize control. However, dedsec has detected the intrusion and is ready to counterattack.

The dedsec network can be modeled as a tree with n nodes and n - 1 edges. Each node has a stability value.

Aiden can choose any chain (i.e. a simple path) in the tree and hack each node along that chain (effectively "extracting" that chain from the tree). Suppose the chosen chain has length m, giving you m nodes.

After the chain is chosen, a battle begins between Aiden and dedsec. They take turns performing moves. In each turn, a player may pick any node from the chain whose current stability value is greater than 0, and reduce its stability by any positive integer amount (subject to the restriction that the stability value does not drop below 0, otherwise the computer will explode). The player who cannot make a move loses the game.

Because dedsec defends from a position of strength, dedsec makes the first move. Aiden, despite his hacking prowess, is at a disadvantage since his phone is dead. He has reached out to you for help. Your task is to determine whether there exists a way for Aiden to choose a chain such that he can secure a win assuming both players play optimally. If no such chain exists because dedsec’s defense is flawless, then Aiden’s fate is sealed.

Hint: When a move consists of subtracting a positive number (up to the current stability value), this is essentially equivalent to a game of Nim played on several piles where the pile sizes are the stability values. Since dedsec moves first, Aiden can win if the initial configuration for the chain results in a losing position for the first mover, that is, if the XOR (nim-sum) of the stability values in the chosen chain is 0.

inputFormat

The first line contains an integer n (the number of nodes in the tree).

The second line contains n space-separated integers, where the i-th integer represents the stability value of node i.

Each of the following n - 1 lines contains two space-separated integers u and v, indicating that there is an undirected edge between node u and node v.

outputFormat

Output a single line containing YES if Aiden can choose a chain where the XOR of the stability values is 0 (ensuring that the first mover, dedsec, is at a disadvantage), or NO otherwise.

sample

3
1 2 3
1 2
2 3

YES