Balanced tree
Given a tree with n vertices, where the vertices are numbered from 1 to n and are painted either red or black. The tree is suspended from the vertex numbered 1.
The tree qualifies as a red-black tree if it satisfies the following conditions:
Each vertex has either 2 or 0 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 determine whether the given tree is a red-black tree. If it is, construct an isomorphic 2-3-4 tree.
Input
The input consists of the number n (1 ≤ n ≤ 10^5), followed by n pairs of numbers. Each i-th pair represents the parent of the i-th vertex and its color (either R for red or B for black). The root's parent is the vertex numbered 1.
Output
Output YES or NO. If the answer is YES, also output the isomorphic 2-3-4 tree. Present the tree by specifying the number of edges and the edges themselves. The vertices should retain the same numbering as in the original tree.