Hide

Problem C
Boxes

There are $N$ boxes, indexed by a number from $1$ to $N$. Each box may (or not may not) be put into other boxes. These boxes together form a tree structure (or a forest structure, to be precise).

You have to answer a series of queries of the following form: given a list of indices of the boxes, find the total number of boxes that the list of boxes actually contain.

Consider, for example, the following five boxes.

\includegraphics[width=0.5\textwidth ]{Boxes}
Figure 1: Sample input
  • If the query is the list “1”, then the correct answer is “5”, because box 1 contains all boxes.

  • If the query is the list “4 5”, then the correct answer is “2”, for boxes 4 and 5 contain themselves and nothing else.

  • If the query is the list “3 4”, then the correct answer is “2”.

  • If the query is the list “2 3 4”, then the correct answer is “4”, since box 2 also contains box 5.

  • If the query is the list “2”, then the correct answer is “3”, because box 2 contains itself and two other boxes.

Input

The first line contains the integer $N$ ($1 \leq N \leq 200\, 000$), the number of boxes.

The second line contains $N$­integers. The $i$th integer is either the index of the box which contains the $i$th box, or zero if the $i$th box is not contained in any other box.

The third line contains an integer $Q$ ($1 \leq Q \leq 100\, 000$), the number of queries. The following $Q$ lines will have the following format: on each line, the first integer $M$ ($1 \leq M \leq 20$) is the length of the list of boxes in this query, then $M$ integers follow, representing the indices of the boxes.

Output

For each query, output a line which contains an integer representing the total number of boxes.

Sample Input 1 Sample Output 1
5
0 1 1 2 2
5
1 1
2 4 5
2 3 4
3 2 3 4
1 2
5
2
2
4
3

Please log in to submit a solution to this problem

Log in