Background

Original problem link: https://oier.team/problems/X6B.

Problem Description

There is an OI problem. This problem has $n$ subtasks, numbered from $1$ to $n$. Subtask $i$ depends on $d_i$ subtasks, whose numbers are $a_{i,1},a_{i,2},\dots,a_{i,d_i}$. It is guaranteed that for all $1\leq i\leq n,1\leq j\leq d_i$, we have $a_{i,j}<i$, i.e., a subtask only depends on subtasks with smaller numbers than itself. Note that a subtask may depend on no subtasks.

A contestant's program can be described as a length-$n$ $0/1$ sequence $p_1,p_2,\dots,p_n$, indicating whether the program can pass subtask $i$.

When judging a program, the judge will consider each subtask in increasing order of its number. When considering subtask $i$:

• If among the subtasks it depends on, there exists a subtask whose status is wrong, then the status of subtask $i$ is wrong.
• Otherwise, the judge tests this subtask. If the contestant's program can pass this subtask, then the status of this subtask is correct; otherwise, it is wrong.

The score of a program is the number of subtasks whose final status is correct after judging.

Now there are $m$ contestants who submitted programs. You need to compute their scores separately.

Input Format

The first line contains an integer $n$, the number of subtasks.

The next $n$ lines: on the $i$-th line, first input an integer $d_i$, the number of subtasks that subtask $i$ depends on; then input $d_i$ integers $a_{i,1},a_{i,2},\dots,a_{i,d_i}$, the indices of the dependent subtasks. It is guaranteed that all $a_{i,j}<i$.

The next line contains an integer $m$, the number of contestant programs.

The next $m$ lines: each line contains $n$ integers. On the $i$-th line, the $j$-th integer $p_{i,j}$ is $0$ meaning the $i$-th contestant's program cannot pass subtask $j$, and $1$ meaning it can pass subtask $j$.

Output Format

Output $m$ lines. On the $i$-th line, output the score of the $i$-th contestant.

3
0
1 1
1 2
3
1 1 1
1 0 1
0 0 0

3
1
0

10
0
1 1
1 2
3 1 2 3
4 1 4 2 3
0
5 6 4 5 2 1
0
1 4
1 9
10
1 0 0 1 1 0 1 0 0 0
1 0 1 0 1 0 1 0 1 0
1 0 1 1 1 1 1 1 0 1
1 1 0 1 1 0 1 1 0 1
1 1 0 1 0 0 0 1 1 1
1 1 0 1 0 1 0 1 1 1
1 0 0 1 0 1 1 1 0 1
1 1 0 1 1 1 0 0 1 1
1 1 1 0 0 0 0 0 1 1
1 0 0 0 1 1 1 0 1 1

1
1
3
3
3
4
3
3
3
2

Hint

Sample Explanation #1

• Contestant 1's program can pass all subtasks, so the results of all $3$ subtasks are correct.
• Contestant 2's program cannot pass subtask $2$, so subtask $2$ will be judged as wrong. Since subtask $3$ depends on subtask $2$, even if contestant 2's program can pass subtask $3$, subtask $3$ will still be judged as wrong. This contestant's judging result has only subtask $1$ correct.
• Contestant 3's program cannot pass any subtask, so the results of all subtasks are wrong.

Constraints

For all testdata, $1\leq n,m\leq 100$, $0\leq d_i<i$, $1\leq a_{i,j}<i$, $0\leq p_{i,j}\leq 1$, and there do not exist $i$ and $j_1\neq j_2$ such that $a_{i,j_1}=a_{i,j_2}$.

There are $10$ test groups in total, with the specific limits as follows:

• For test groups $1,2$, $n=1$.
• For test groups $3,4,5$, for all $i$, $d_i\leq 1$.
• For the other test groups, there are no additional constraints.

Translated by ChatGPT 5