Tree Games
Two-player game defined by its tree. Rivals make moves in turn. The first player starts the game. The game ends or tie, or win one of the players. The leaves of the tree of this game can have values equal to one of three numbers: +1 - win the first player, -1 - a victory the second player, 0 - a draw. Your task - to determine who will win, if both opponents follow the correct strategy.
Input
Tree nodes are numbered by consecutive integers. The root of the tree always has the number 1. The first line contains a positive integer N - the number of nodes in the tree game (N ≤ 1000). Next N-1 line describes the units - one row for each node (except the first). The second line contains a description of the second node of the tree, the third - the third node, etc. If the node is a leaf, the first character string - L, then goes blank, then the number of parent node has a space and result of the game (+1 - win the first player to -1 - the victory of the second, 0 - tie). If the node is internal, then the line contains N - the first character, followed by a space and the number of parent.
Output
The output file output +1 if the first player wins, and -1 if the second, and 0 - in the event of a draw outcome.