У Рудольфа есть любимая собачка, которую зовут Байер. Как и всякий ответственный хозяин, Рудольф старается воспитывать своего питомца и учит его выполнять различные команды. Однако традиционные трюки вроде «_Сидеть_» и «_Апорт_» не очень-то и впечатляют Рудольфа, поэтому он придумал для Байера кое-что получше. Рудольф — большой фанат структур данных, в связи с чем он предлагает Байеру рисовать красно-чёрные деревья.
Красно-чёрное дерево — это древовидная структура данных, имеющая следующие особенности:
Сегодня Рудольф решил пообедать в своём любимом кафе. К сожалению, туда не пускают с животными, поэтому Байеру придётся остаться дома. Чтобы питомцу не было грустно, Рудольф поручил ему составить примеры красно-чёрных деревьев. Байер с радостью согласился и с энтузиазмом взялся за работу.
Через три часа Рудольф вернулся из кафе сытый и довольный. К своему удивлению, он обнаружил, что Байер успел нарисовать огромное количество красно-чёрных деревьев: среди них были маленькие, средние, большие и даже очень большие. Рудольф смог визуально оценить только деревья небольшого размера и нашёл несколько ошибок. А вот проверить остальные деревья оказалось очень сложно, поэтому Рудольф попросил вас автоматизировать оценку трудов Байера.
Первая строка содержит число n (1 ≤ n ≤ 105) — количество внутренних узлов красно-чёрного дерева.
Следующие n строк описывают внутренние узлы. Каждая из них содержит строку ci, целое число ki и целое число pi (, 1 ≤ ki, pi ≤ 1018) — цвет узла, ключ узла и ключ родителя, соответственно. Для корневого узла pi = - 1.
Гарантируется, что описанный во входных данных граф является деревом и имеет корень.
Выведите «_YES_» (без кавычек), если входные данные содержат корректное описание красно-чёрного дерева (с учётом добавления листовых узлов). В противном случае выведите «_NO_» (без кавычек).
## Входные Данные
Первая строка содержит число n (1 ≤ n ≤ 105) — количество внутренних узлов красно-чёрного дерева. Следующие n строк описывают внутренние узлы. Каждая из них содержит строку ci, целое число ki и целое число pi (, 1 ≤ ki, pi ≤ 1018) — цвет узла, ключ узла и ключ родителя, соответственно. Для корневого узла pi = - 1.Гарантируется, что описанный во входных данных граф является деревом и имеет корень.
## Выходные Данные
Выведите «_YES_» (без кавычек), если входные данные содержат корректное описание красно-чёрного дерева (с учётом добавления листовых узлов). В противном случае выведите «_NO_» (без кавычек).
## Примеры
Входные данные5red 30 40black 20 -1black 10 20black 40 20red 50 40Выходные данныеYESВходные данные5red 3 4red 5 4black 2 -1black 1 2red 4 2Выходные данныеNO
[samples]
**Definitions**
Let $ n \in \mathbb{Z} $ be the number of internal nodes.
Let $ V = \{v_1, \dots, v_n\} $ be the set of internal nodes, where each node $ v_i $ is characterized by:
- $ c_i \in \{\text{red}, \text{black}\} $: color of the node,
- $ k_i \in \mathbb{Z} $: key of the node,
- $ p_i \in \mathbb{Z} \cup \{-1\} $: key of the parent node ($ p_i = -1 $ iff $ v_i $ is root).
Let $ T $ be the tree structure induced by parent-child relationships. Add external (leaf) nodes (black, key-less) as children where needed to satisfy red-black tree properties.
**Constraints**
1. $ 1 \leq n \leq 10^5 $
2. $ 1 \leq k_i, p_i \leq 10^{18} $ for all $ i $, and $ p_i = -1 $ for exactly one node (the root).
3. The graph is a tree with unique root.
4. All keys are distinct.
**Objective**
Determine whether $ T $, with added black leaf nodes, satisfies all red-black tree properties:
1. Every node is either red or black.
2. The root is black.
3. Every leaf (external node) is black.
4. If a node is red, then both its children are black.
5. For each node, all simple paths from it to descendant leaves contain the same number of black nodes (black-height).
Output "YES" if all properties hold; otherwise, output "NO".