e-olymp
Задачи

Дерево игры

Дерево игры

prb659 Игра для двух игроков определяется её деревом. Соперники делают ходы по очереди. Первый игрок начинает игру. Игра кончается или вничью, или победой одного из игроков. Листья дерева этой игры могут иметь значения, равные одному из трёх чисел: +1 - победа первого игрока, -1 - победа второго игрока, 0 - ничья. Ваша задача - определить, кто выиграет, если оба противника следуют правильной стратегии.

Входные данные

Узлы дерева пронумерованы последовательными целыми числами. Корень дерева всегда имеет номер 1. Первая строка входного файла содержит натуральное N - число узлов в дереве игры (N1000). Следующая N-1 строка описывает узлы - одна строка для каждого узла (за исключением первого). Вторая строка содержит описание второго узла дерева, третья - третьего узла и т.д. Если узел является листом, первый символ строки - L, затем идёт пробел, затем номер родительского узла, ещё пробел и результат игры (+1 - победа первого игрока, -1 - победа второго, 0 - ничья). Если узел внутренний, то строка содержит N - первый символ, затем пробел и номер родительского узла.

Выходные данные

В выходной файл выведите +1, если выигрывает первый игрок, -1, если второй, и 0 - в случае ничейного исхода.

Лимит времени 1 секунда
Лимит использования памяти 64 MiB
Входные данные
Sample 1
7
N 1
N 1
L 2 -1
L 2 +1
L 3 +1
L 3 +1 

Sample 2
7
N 1
N 1
L 2 -1
L 2 +1
L 3 +1
L 3 0 

Sample 3
18
N 1
N 1
N 2
L 2 +1
N 3
L 3 +1
L 3 +1
L 4 -1
L 4 +1
N 4
N 6
L 6 -1
L 6 -1
L 11 -1
L 11 +1
L 12 +1
L 12 -1
Выходные данные
Sample 1
+1

Sample 2
0

Sample 3
+1