[BalticOI 2020 Day2] 病毒
题目背景
本题数据为删减版(去掉了最后的 $6$ 组数据),完整版请去 [CF1387C](https://www.luogu.com.cn/problem/CF1387C) 提交。
题目描述
给定一种病毒,为了方便,我们用 $0$ 到 $G-1$ 的整数描述他的基因序列。
现在这个病毒可以进行变异,有一些变异规则,每个变异规则可以让基因序列上的某个数变成某个片段,如果用变异规则让基因序列变成了全部为 $0$ 和 $1$ 的序列,那么这个病毒就变异完成了。
病毒可以通过抗体进行检测,比如 $01011$ 就可以检测到 $0101110$,但不能检测到 $110110$。
对于从 $2$ 到 $G-1$ 中的基因,科学家想知道,是否能通过任意一组给定的抗体检测到这个基因变异形成的其他所有基因,不能的话,那么求不能检测到的基因中的最短长度。
输入输出格式
输入格式
第一行三个整数 $G,N,M$ 代表基因数,变异规则数和抗体数。
接下来 $N$ 行每行首先两个整数 $a,k$,然后接着 $k$ 个整数 $b_i$,代表 $a$ 可以通过这个变异规则变为 $b_1,b_2,\cdots,b_k$ 这个片段,保证 $2$ 和 $G-1$ 都至少在每个规则中的 $a$ 中出现一次。
接下来 $M$ 行每行首先一个整数 $l$ 代表抗体长度,接下来 $l$ 个整数 $c_i$ 描述这个抗体。
输出格式
$G-2$ 行第 $i$ 行代表 $i$ 基因以及其所有变异到的基因是否都可以被任意一组抗体检测到,如果可以,输出一个字符串 `YES`,如果不可以,首先一个字符串 `NO`,接下来一个整数代表不能检测到的基因中的最短长度。
输入输出样例
输入样例 #1
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
输出样例 #1
NO 2
NO 4
NO 9
YES
说明
#### 数据规模与约定
**本题采用捆绑测试。**
- 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):无特殊限制。
对于 $100\%$ 的数据,$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$。
**本题强制 $O2$ 优化。**