Problem Description
There are N boxes, indexed by a number from 1 to N. Each box may (or may not) be placed into other boxes. These boxes together form a tree structure, or a forest structure consisting of multiple independent trees.
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.
For example, consider 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.
Limits
Subtask 1 (13%): 1 ≤ N ≤ 2000, 0 ≤ Q ≤ 2000, M = 1 for all queries.
Subtask 2 (22%): 1 ≤ N ≤ 2000, 0 ≤ Q ≤ 2000, Sum of M ≤ 2000000 for all testcases.
Subtask 3 (29%): 1 ≤ N ≤ 200000, 0 ≤ Q ≤ 200000, 1 ≤ M ≤ 2 for all queries.
Subtask 4 (36%): 1 ≤ N ≤ 200000, 0 ≤ Q ≤ 200000, Sum of M ≤ 2000000 for all testcases.
Subtask 5 (0%): Sample Testcase.
Input
The first line of input will contain one integer N, the number of boxes.
The second line contains N integers. The ith integer is either the index of the box which contains the ith box, or 0 if the ith box is not contained in any other box.
The third line contains an integer Q, the number of queries.
The following Q lines will have the following format: on each line, the first integer M is the length of the list of boxes in this query. Then, M space separated integers will follow on the same line, representing the indices of the boxes.
Output
For each query, output a line which contains an integer representing the total number of boxes.
Sample Testcase 1
Input
5
0 1 1 2 2
5
1 1
2 4 5
2 3 4
3 2 3 4
1 2
Output
5
2
2
4
3
Credits
Task statement from 2016 ACM ICPC Asia Hong Kong Regional, sourced from Kattis. Testcases and subtasks are self-created.