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.
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.
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.
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 |