Tree Games#659
Two-player game defined by its tree. Rivals make moves in turn, and the first player starts the game. The game ends either with a draw or a win for one of the players. The leaves of the game tree can have one of three values: +1 — first player's victory, -1 — second player's victory, 0 — draw. Your task is to determine who will win if both players play optimally.
Tree nodes are numbered with consecutive integers, and the root of the tree always has the number . The first line contains a positive integer — the number of nodes in the tree (N \leq 1000). The next N - 1 lines describe the nodes, one line for each node (except the root). The second line describes the second node of the tree, the third line describes the third node, and so on. If a node is a leaf, the line starts with L, followed by a space, then the parent node's number, another space, and the result of the game (+1 — first player's win, -1 — second player's win, 0 — draw). If a node is internal, the line starts with N, followed by a space and the parent node's number.
Print +1 if the first player wins, -1 if the second player wins, and 0 in the case of a draw.
Example 1