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