У Рудольфа есть любимая собачка, которую зовут Байер. Как и всякий ответственный хозяин, Рудольф старается воспитывать своего питомца и учит его выполнять различные команды. Однако традиционные трюки вроде «Сидеть» и «Апорт» не очень-то и впечатляют Рудольфа, поэтому он придумал для Байера кое-что получше. Рудольф — большой фанат структур данных, в связи с чем он предлагает Байеру рисовать красно-чёрные деревья.
Красно-чёрное дерево — это древовидная структура данных, имеющая следующие особенности:
- узлы дерева делятся на внутренние и листовые;
- каждый внутренний узел имеет уникальный целочисленный ключ и двух потомков; листовые узлы ключей и потомков не имеют;
- по ключам внутренние узлы образуют двоичное дерево поиска;
- каждый узел имеет цвет — красный или чёрный;
- корень дерева и листовые узлы являются чёрными;
- родитель любого красного узла является чёрным;
- все простые пути от любого узла до листовых узлов, являющихся его потомками, содержат одинаковое количество чёрных узлов.
Сегодня Рудольф решил пообедать в своём любимом кафе. К сожалению, туда не пускают с животными, поэтому Байеру придётся остаться дома. Чтобы питомцу не было грустно, Рудольф поручил ему составить примеры красно-чёрных деревьев. Байер с радостью согласился и с энтузиазмом взялся за работу.
Через три часа Рудольф вернулся из кафе сытый и довольный. К своему удивлению, он обнаружил, что Байер успел нарисовать огромное количество красно-чёрных деревьев: среди них были маленькие, средние, большие и даже очень большие. Рудольф смог визуально оценить только деревья небольшого размера и нашёл несколько ошибок. А вот проверить остальные деревья оказалось очень сложно, поэтому Рудольф попросил вас автоматизировать оценку трудов Байера.
Первая строка содержит число 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
