Tree Queries

1

1 votes
Ready, Graph, Medium, Algorithms, Approved
Problem

Devu and Churu like to play with trees a lot. Today, they have a rooted unbalanced K-ary tree T consisting of N nodes and each node in the tree is labeled uniquely with the integers from 1 to N. Node with label 1 is the root of the tree T

To play with this tree, They have decided to perform Q operations on their tree T. In each operation, they shall be given a list of K nodes. Now, they need to find for all the nodes in this list, a node X, such that node X is an ancestor of all nodes in the given list, and the depth of node X is highest among all possible ancestors of the nodes in the list.

Please refer sample test case for better understanding of the problem.

Input:

The first line of the input contains 2 space separated integers N and Q denoting the number of nodes in the tree T and number of operations to be performed. Each of the next N1 lines of input contains a single integer where the integer in the ith line is the parent of node with label i+1

Each of the next 2×Q lines of input contains Q operations where each operation spans over 2 lines and has following format :

  • The first line of each operation contains an integer K denoting the number of nodes in the given operation.
  • Second line of each operation contains K space separated integers denoting labels of nodes over which you need to perform given operation.

Output

For each of the Q operation, Print the required answer in a new line.

Constraints

  • 1 ≤ N, Q ≤ 105
  • 1 ≤ K ≤ N
  • sum of K over all operations does not exceed 105
  • Given nodes in any operation are labelled with integers from 1 to N
Sample Input
5 5
1
1
2
2
2
4 5
1
2
3
2 4 5
3
3 4 5
5
1 2 3 4 5



Sample Output
2
2
2
1
1
Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation

enter image description here

This is the tree for the sample. For the first query, we need to find the ancestors of node 4 and 5, that is located at ht highest level. All the ancestors of node 4 and 5 include nodes 2 and 1, out of which node 2 is located at the highest level.

So, the answer to the first query is 2.

Editor Image

?