Background

Related multiple-choice and true/false problems: https://ti.luogu.com.cn/problemset/1140.

Problem Description

A company has $N$ employees, numbered from $0$ to $N-1$. Among them, employee $0$ is the boss, and every other employee has exactly one direct supervisor. Assume that the direct supervisor of employee $i$ is $f_i$.

The company has strict management rules: each employee can only be managed by themselves, their direct supervisor, or an indirect supervisor. More precisely, employee $x$ can manage employee $y$ if and only if $x=y$, or $x=f_y$, or $x$ can manage $f_y$. In particular, the boss (employee $0$) can only be managed by themselves and cannot be managed by any other employee.

Now, some colleagues want to work together. They want to find one colleague to host the collaboration, and this person must be able to manage all colleagues participating in the collaboration. If multiple employees satisfy this condition, they want the one with the largest index. Can you help them?

Input Format

The first line contains an integer $N$, the number of employees.

The second line contains $N-1$ positive integers separated by spaces: $f_1, f_2, \dots, f_{N-1}$.

The third line contains an integer $Q$, meaning there are $Q$ collaborations to arrange.

The next $Q$ lines each describe one collaboration. Each line starts with an integer $m$ ($2 \leq m \leq N$), the number of employees participating in this collaboration, followed by $m$ integers giving the indices of the participating employees (it is guaranteed that the indices are valid and all distinct).

It is guaranteed that the company structure is valid, i.e., there is no employee who is their own direct or indirect supervisor.

Output Format

Output $Q$ lines. Each line contains one integer, the chosen host for the corresponding collaboration.

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

2
2
0

7
0 1 0 2 1 2
5
2 4 6
2 4 5
3 4 5 6
4 2 4 5 6
2 3 4

2
1
1
1
0

Hint

Sample Explanation 1

For the first collaboration, employees $3,4$ have a common supervisor $2$, who can host the collaboration.

For the second collaboration, employee $2$ themselves can manage all participants.

For the third collaboration, only the boss $0$ can manage all employees.

Constraints

For $25\%$ of the testdata, $N \leq 50$.

For $50\%$ of the testdata, $N \leq 300$.

For all testdata, $3 \leq N \leq 10^5$, $Q \leq 100$, $m \leq 10^4$.

2024/2/8 Added one set of hack testdata.

Translated by ChatGPT 5