Збалансоване дерево#2950
Дано дерево з коренем у вершині , яке має вершин, вершини пронумеровані від до і пофарбовані в червоний або чорний колір.
Дерево називається червоно-чорним, якщо виконується наступне:
Кожна вершина має або , або дітей.
Усі листки чорні.
Кількість чорних вершин на будь-якому шляху від кореня до листка — однакова.
У червоної вершини не може бути червоного батька.
Ваша задача — перевірити, чи є задане дерево червоно-чорним. Якщо так, побудуйте ізоморфне -- дерево.
Перший рядок містить (1 \leq n \leq 10^5). Кожна з наступних пар задає батька -ї вершини та її колір (літера — червоний, — чорний). Батьком кореня є вершина під номером .
Виведіть YES або NO. Якщо відповідь YES, також виведіть ізоморфне -- дерево у такому форматі: кількість ребер, а потім самі ребра. Нумерація вершин повинна відповідати оригінальному дереву.
Приклад 1