Matcom Online Grader

Dos amigos están jugando con un árbol de $N$ nodos. Al inicio del juego en cada nodo hay un conjunto de piedras. Después ambos jugadores van turnándose alternadamente hasta que no puedan hacer más movimientos. En un turno un jugador selecciona un nodo y mueve dos piedras desde él a uno de sus ancestros. La raíz del árbol siempre es el nodo con identificador $1$. El primer jugador que no puede hacer ningún movimiento pierde. Los dos amigos son muy buenos jugadores y siempre van a seguir la mejor estrategia para intentar ganar. Si sabemos cuantas piedras hay al inicio en cada pila queremos predecir quién gana el juego.

La primera línea de la entrada consiste en un número entero $N (1 \le N \le 10 ^ 5)$ que indica la cantidad de nodos en el árbol. La siguiente línea contiene $N$ enteros $p_i (1 \le p_i \le 10 ^ 9)$ separados por un espacio describiendo la cantidad de piedras en cada nodo. Después se dan las aristas del árbol en $N - 1$ líneas, cada una contiene dos enteros separados por un espacio.

Por cada caso se debe imprimir el ganador del juego. Si el primer jugador siempre puede ganar entonces debe imprimir “Gana el primer jugador.”, en caso contrario la respuesta debe ser “Gana el segundo jugador.”