В этой задаче мы будем работать с подвешенными бинарными деревьями. Напомним, что дерево называется подвешенным бинарным, если в нем есть выделенный корень, а у каждой вершины не более двух детей.
Сопоставим каждой вершине дерева один из двух цветов — белый или синий — и назовем такое сопоставление раскраской дерева. Раскраску назовем разнообразной, если у каждой вершины есть сосед (ребенок или родитель), покрашенный не в тот же цвет, что и сама вершина. Можно показать, что у любого дерева из не менее чем двух вершин существует разнообразная раскраска.
Дисбалансом раскраски назовем абсолютную разность между числом белых и синих вершин в ней.
Теперь к задаче. Изначально дерево состоит из одной вершины с номером \(1\), являющейся его корнем. Далее для каждого \(i\) от \(2\) до \(n\) в дереве появляется новая вершина \(i\), которая становится ребенком вершины \(p_i\). Гарантируется, что после каждого добавления дерево будет оставаться бинарным с корнем в вершине \(1\), то есть у каждой вершины будет не более двух детей.
После каждого добавления вершины нужно вывести минимальное возможное значение дисбаланса по всем возможным разнообразным раскраскам текущего дерева. Более того, после добавления последней вершины с номером \(n\) нужно также вывести саму разнообразную раскраску с минимальным дисбалансом.
Выходные данные
Для каждого набора входных данных выведите \(n-1\) целое число — минимальное возможное значение дисбаланса по всем возможным разнообразным раскраскам дерева после добавления в него вершин \(2, 3, \ldots, n\).
Далее выведите строку из \(n\) символов «w» и «b», описывающую разнообразную раскраску с минимальным дисбалансом для всего дерева целиком после добавления вершины \(n\): \(i\)-й символ строки должен быть равен «w», если вершина \(i\) покрашена в белый цвет, и «b», если в синий. Абсолютная разность между числом символов «w» и «b» должна быть равна последнему выведенному числу. У каждой вершины должен быть родитель или ребенок, покрашенный не в тот же цвет, что и сама вершина.
Примечание
Примеры разнообразных раскрасок с минимальным дисбалансом для всех промежуточных деревьев в первом наборе входных данных представлены на рисунке ниже:
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
7
1 2 2 1 5 5
8
1 2 3 4 5 6 7
|
0
1
2
1
0
1
wbwwwbb
0
1
0
1
0
1
0
wbwbwbwb
|