Background

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

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 a direct manager. We assume that the direct manager of employee $i$ is $f_i$.

The company has a strict management system: each employee can only be managed by themselves, or by their direct manager, or by an indirect manager. Specifically, 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 manage 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. This colleague must be able to manage all colleagues participating in the collaboration. If multiple employees satisfy this condition, they want the employee with the largest index. Can you help them?

Input Format

The first line contains an integer $N$, representing 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$, representing that there are $Q$ collaborations to arrange.

The next $Q$ lines each describe a collaboration. Each line starts with an integer $m$ ($2 \le m \le N$), representing the number of employees participating in this collaboration; then follow $m$ integers, representing the indices of the participating employees in order (it is guaranteed that the indices are valid and not repeated).

It is guaranteed that the company structure is valid, meaning that there does not exist any employee who is their own direct or indirect manager.

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 manager $2$, who can host the collaboration.

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

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

Constraints

For $50\%$ of the test points, it is guaranteed that $N \leq 50$.

For all test points, it is guaranteed that $3 \leq N \leq 300$, $Q \leq 100$.

On 2024/1/28, a set of hack testdata was added.

Translated by ChatGPT 5