Nearest Ancestor Query with Specific Color

You are given a tree with \( n \) nodes numbered from \( 0 \) to \( n-1 \). Each node has a color assigned from \( 0 \) to \( n-1 \). You are also given \( q \) online queries. For each query, you are given two integers \( x \) and \( c \). Your task is to find the nearest ancestor of node \( x \) (including itself) whose color is exactly \( c \). More formally, if we define an ancestor as any node in the path from \( x \) to the root (where the root is node \( 0 \)), you must report the one with the maximum depth (i.e. closest to \( x \)). If no such ancestor exists, print \(-1\).

Note: The colors of the nodes have been randomly permuted (a uniform random permutation was applied) after the tree was generated.

Input Format:

• The first line contains two integers \( n \) and \( q \), the number of nodes and the number of queries.
• The second line contains \( n-1 \) integers, where the \( i^{th} \) integer (for \( i = 1 \) to \( n-1 \)) denotes the parent of node \( i \). The tree is rooted at node \( 0 \), which has no parent.
• The third line contains \( n \) integers, where the \( i^{th} \) integer denotes the color of node \( i \) (after the random permutation).
• The following \( q \) lines each contain two integers \( x \) and \( c \), representing a query.

Output Format:

• For each query, output a single integer representing the index of the nearest ancestor of \( x \) whose color is \( c \). If no such node exists, output \(-1\).

inputFormat

The input consists of:

1. A line with two integers \( n \) and \( q \).
2. A line with \( n-1 \) integers \( p_1, p_2, ..., p_{n-1} \) where \( p_i \) is the parent of node \( i \) for \( i \ge 1 \). Node \( 0 \) is the root and has no parent.
3. A line with \( n \) integers representing the colors of the nodes (after a random permutation).
4. \( q \) lines each containing two integers \( x \) and \( c \) representing a query.

outputFormat

For each query, print a single integer — the index of the nearest ancestor of node \( x \) having color \( c \). If such an ancestor does not exist, print \(-1\).

sample

5 3
0 0 1 1
1 3 2 3 0
3 3
4 2
2 1

3
-1
0