# Shortest paths - interesting graph problems

# Mancunian And Colored Tree

After a hectic week at work, Mancunian and Liverbird decide to go on a fun weekend camping trip. As they were passing through a forest, they stumbled upon a unique tree of **n** nodes. Vertices are numbered from
**1** to **n**.

Each node of the tree is assigned a color (out of **c** possible colors). Being bored, they decide to work together (for a change) and test their reasoning skills. The tree is rooted at vertex **1**. For each node, they want to find its closest ancestor having the same color.

#### Input

The first line contains two integers **n** and **c** (**1** ≤ **n**, **c** ≤ `10`

) denoting the number of vertices in the tree and the number of possible colors. ^{5}

The second line contains **n** - **1** integers. The **i**-th integer denotes the parent of the **i** + **1** - th vertex.

The third line contains **n** integers, denoting the colors of the vertices. Each color lies between **1** and **c** inclusive.

#### Output

Print **n** space-separated integers. The **i**-th integer is the vertex number of lowest ancestor of the
**i**-th node which has the same color. If there is no such ancestor, print **-1** for that node.

5 4 1 1 3 3 1 4 2 1 2

-1 -1 -1 1 3