Задачі
Сбалансированное дерево
Сбалансированное дерево
Дано подвешенное за вершину с номером \textbf{1 }дерево из \textbf{n }вершин. Вершины дерева нумеруются от \textbf{1 }до \textbf{n }и покрашены в красный и черный цвета.
Дерево называется красно-черным, если:
\begin{itemize}
\item У каждой вершины количество детей или \textbf{2 }или \textbf{0}.
\item Все листья черные
\item На пути от корня до любого из листьев одинаковое количество черных вершин
\item Отцом красной вершины не может быть красная вершина
\end{itemize}
Ваша задача - проверить, является ли данное вам дерево красно-черным. Если же является, то нужно построить изоморфное ему \textbf{2}-\textbf{3}-\textbf{4}-дерево.
\InputFile
Число \textbf{n }(\textbf{1 }≤ \textbf{n }≤ \textbf{10^5}), далее \textbf{n }пар чисел. \textbf{i}-я пара чисел - отец \textbf{i}-й вершины и ее цвет (буква \textbf{R }= \textbf{red} или буква\textbf{ B} = \textbf{black}). Отец корня - вершина с номером \textbf{1}.
\OutputFile
Выведите \textbf{YES }или \textbf{NO}. Если ответ \textbf{YES}, выведите \textbf{2}-\textbf{3}-\textbf{4} дерево изоморфное исходному. Дерево выведите в следующем формате: количество ребер и ребра. Нумерация вершин должна быть такая же, как и в исходном дереве.
Вхідні дані #1
1 -1 R
Вихідні дані #1
NO