Description

A virus is given. For convenience, we use the integers from $0$ to $G-1$ to describe its gene sequence.

Now this virus can mutate. There are some mutation rules. Each mutation rule can replace a number in the gene sequence with a certain fragment. If, by applying mutation rules, the gene sequence becomes a sequence consisting only of $0$ and $1$, then the mutation of the virus is completed.

The virus can be detected by antibodies. For example, $01011$ can detect $0101110$, but it cannot detect $110110$.

For genes from $2$ to $G-1$, scientists want to know whether any given set of antibodies can detect all other genes that can be formed by mutations from this gene. If not, find the minimum length among the genes that cannot be detected.

Input Format

The first line contains three integers $G, N, M$, representing the number of genes, the number of mutation rules, and the number of antibodies.

In the next $N$ lines, each line starts with two integers $a, k$, followed by $k$ integers $b_i$, meaning that $a$ can be transformed by this mutation rule into the fragment $b_1, b_2, \cdots, b_k$. It is guaranteed that both $2$ and $G-1$ appear at least once among the $a$ values in all rules.

In the next $M$ lines, each line starts with an integer $l$ representing the antibody length, followed by $l$ integers $c_i$ describing the antibody.

Output Format

Output $G-2$ lines. Line $i$ corresponds to gene $i$ and all genes it can mutate into. If all of them can be detected by any given set of antibodies, output the string YES. Otherwise, output the string NO first, followed by an integer representing the minimum length among the genes that cannot be detected. It is guaranteed that for all testdata, this value is less than $2^{63}$.

6 6 2
2 2 0 1
3 3 2 0 0
3 2 1 3
4 4 0 3 1 2
5 2 2 1
5 1 5
2 1 1
5 0 0 1 0 0

NO 2
NO 4
NO 9
YES

Hint

Constraints

This problem uses bundled tests.

• Subtask 1 (11 pts): $M=0$.
• Subtask 2 (14 pts): $N = G-2$.
• Subtask 3 (25 pts): $M=1$.
• Subtask 4 (32 pts): $\sum l \le 10$.
• Subtask 5 (18 pts): No special constraints.

For $100\%$ of the testdata, $G > 2$, $N \ge G-2$, $M \ge 0$. $2 \le a <G$, $k \ge 1$, $0 \le b_i<G$, $\sum k \le 100$, $l \ge 1$, $0 \le c_i \le 1$, $\sum l\le 50$.

This problem enforces $O2$ optimization.

Translated by ChatGPT 5