eolymp
bolt
Try our new interface for solving problems
Məsələlər

Манкунианец и цветное дерево

Манкунианец и цветное дерево

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

После напряженной недели на работе, жители Манчестера и Ливерпуля решили пойти в поход на выходные. Когда они проходили по лесу, они наткнулись на уникальное дерево, состоящее из 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ə

Giriş verilənləri #1
5 4
1 1 3 3
1 4 2 1 2
Çıxış verilənləri #1
-1 -1 -1 1 3