A. Рудольф и дрессировка
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
input.txt
вывод
output.txt

У Рудольфа есть любимая собачка, которую зовут Байер. Как и всякий ответственный хозяин, Рудольф старается воспитывать своего питомца и учит его выполнять различные команды. Однако традиционные трюки вроде «Сидеть» и «Апорт» не очень-то и впечатляют Рудольфа, поэтому он придумал для Байера кое-что получше. Рудольф — большой фанат структур данных, в связи с чем он предлагает Байеру рисовать красно-чёрные деревья.

Красно-чёрное дерево — это древовидная структура данных, имеющая следующие особенности:

  • узлы дерева делятся на внутренние и листовые;
  • каждый внутренний узел имеет уникальный целочисленный ключ и двух потомков; листовые узлы ключей и потомков не имеют;
  • по ключам внутренние узлы образуют двоичное дерево поиска;
  • каждый узел имеет цвет — красный или чёрный;
  • корень дерева и листовые узлы являются чёрными;
  • родитель любого красного узла является чёрным;
  • все простые пути от любого узла до листовых узлов, являющихся его потомками, содержат одинаковое количество чёрных узлов.

Сегодня Рудольф решил пообедать в своём любимом кафе. К сожалению, туда не пускают с животными, поэтому Байеру придётся остаться дома. Чтобы питомцу не было грустно, Рудольф поручил ему составить примеры красно-чёрных деревьев. Байер с радостью согласился и с энтузиазмом взялся за работу.

Через три часа Рудольф вернулся из кафе сытый и довольный. К своему удивлению, он обнаружил, что Байер успел нарисовать огромное количество красно-чёрных деревьев: среди них были маленькие, средние, большие и даже очень большие. Рудольф смог визуально оценить только деревья небольшого размера и нашёл несколько ошибок. А вот проверить остальные деревья оказалось очень сложно, поэтому Рудольф попросил вас автоматизировать оценку трудов Байера.

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

Первая строка содержит число n (1 ≤ n ≤ 105) — количество внутренних узлов красно-чёрного дерева.

Следующие n строк описывают внутренние узлы. Каждая из них содержит строку ci, целое число ki и целое число pi (, 1 ≤ ki, pi ≤ 1018) — цвет узла, ключ узла и ключ родителя, соответственно. Для корневого узла pi =  - 1.

Гарантируется, что описанный во входных данных граф является деревом и имеет корень.

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

Выведите «YES» (без кавычек), если входные данные содержат корректное описание красно-чёрного дерева (с учётом добавления листовых узлов). В противном случае выведите «NO» (без кавычек).

Примеры
Входные данные
5
red 30 40
black 20 -1
black 10 20
black 40 20
red 50 40
Выходные данные
YES
Входные данные
5
red 3 4
red 5 4
black 2 -1
black 1 2
red 4 2
Выходные данные
NO