Манкунианец и цветное дерево
Манкунианец и цветное дерево
После напряженной недели на работе, жители Манчестера и Ливерпуля решили пойти в поход на выходные. Когда они проходили по лесу, они наткнулись на уникальное дерево, состоящее из n вершин. Вершины пронумерованы числами от 1 до n.
Каждой вершине дерева поставлен в соответствие цвет (из c возможных цветов). Чтобы побороть скуку, они решили проверить вместе свои навыки рассуждения. Корнем дерева является вершина 1. Для каждой вершины они решили найти ближайшего предка, цвет которого совпадает с цветом вершины.
Giriş verilənləri
Первая строка содержит два целых числа n и c~(1 \le n, c \le 10^5) — количество вершин в дереве и количество возможных цветов.
Вторая строка содержит n - 1 число. i-ое число указывает на отца i + 1 - ой вершины.
Третья строка содержит n целых чисел, задающих цвета вершин. Значения цветов лежат в промежутке от 1 до c включительно.
Çıxış verilənləri
В одной строке выведите n чисел. i-ым числом является вершина, являющаяся ближайшим предком i-ой вершины, имеющей такой же цвет. Если такого предка для вершины не существует, то выведите -1.
Nümunə
5 4 1 1 3 3 1 4 2 1 2
-1 -1 -1 1 3