Balanced tree#2950
Given a tree rooted at vertex with vertices, where the vertices are numbered from to and are colored either red or black.
A tree is called a red-black tree if it satisfies the following conditions:
Each vertex has either or children.
All leaves are black.
Every path from the root to any leaf contains the same number of black vertices.
A red vertex cannot have a red parent.
Your task is to check whether the given tree is a red-black tree. If it is, construct an isomorphic -- tree.
The first line contains (1 \leq n \leq 10^5). Each of the next pairs represents the parent of the -th vertex and its color (letter for red or for black). The parent of the root is the vertex numbered .
Output YES or NO. If the answer is YES, also output the isomorphic -- tree in the following format: the number of edges, followed by the edges. The vertices must be numbered as in the original tree.
Example 1