Задачи
Манкунианец и цветное дерево
Манкунианец и цветное дерево
После напряженной недели на работе, жители Манчестера и Ливерпуля решили пойти в поход на выходные. Когда они проходили по лесу, они наткнулись на уникальное дерево, состоящее из $n$ вершин. Вершины пронумерованы числами от $1$ до $n$.
Каждой вершине дерева поставлен в соответствие цвет (из $c$ возможных цветов). Чтобы побороть скуку, они решили проверить вместе свои навыки рассуждения. Корнем дерева является вершина $1$. Для каждой вершины они решили найти ближайшего предка, цвет которого совпадает с цветом вершины.
\InputFile
Первая строка содержит два целых числа $n$ и $c~(1 \le n, c \le 10^5)$ --- количество вершин в дереве и количество возможных цветов.
Вторая строка содержит $n - 1$ число. $i$-ое число указывает на отца $i + 1$ - ой вершины.
Третья строка содержит $n$ целых чисел, задающих цвета вершин. Значения цветов лежат в промежутке от $1$ до $c$ включительно.
\OutputFile
В одной строке выведите $n$ чисел. $i$-ым числом является вершина, являющаяся ближайшим предком $i$-ой вершины, имеющей такой же цвет. Если такого предка для вершины не существует, то выведите $-1$.
Входные данные #1
5 4 1 1 3 3 1 4 2 1 2
Выходные данные #1
-1 -1 -1 1 3