题目描述
题目译自 BalticOI 2020 Day2 C「Viruses」
科学家研究病毒的基因突变。病毒的基因由一个数列组成,当中的数字为 0∼G−1。根据突变表,当突变发生时,病毒基因序列中的一个数字就会被相应的数字串所取代。当病毒仅由 0,1 组成时,突变终止。
例如,按照如下的突变表所示:
2→⟨0 1⟩
3→⟨2 0 0⟩
3→⟨1 3⟩
4→⟨0 3 1 2⟩
5→⟨2 1⟩
5→⟨5⟩
那么最初基因为一个 4 的病毒可能会发生以下突变:
⟨4⟩→⟨0 3 1 2⟩→⟨0 2 0 0 1 2⟩→⟨0 0 1 0 0 1 2⟩→⟨0 0 1 0 0 1 0 1⟩
或以另一种方式:
⟨4⟩→⟨0 3 1 2⟩→⟨0 1 3 1 2⟩→⟨0 1 3 1 0 1⟩→⟨0 1 2 0 0 1 0 1⟩→⟨0 1 0 1 0 0 1 0 1⟩
病毒由抗体来识别。抗体的识别方法是检查病毒中是否含有一段特定的 0,1组成的片段。例如,抗体的特定片段为 ⟨0 0 1 0 0⟩,那么它可以检测到病毒 ⟨0 0 1 0 0 1 0 1⟩,但却无法检测出病毒 ⟨0 1 0 1 0 0 1 0 1⟩。
对于 2∼G−1 的每一个基因,科学家们都想知道一组给定的抗体能否检测出通过突变最终产生的所有病毒。如果无法全部检测,他们就想知道最短的不能检测的病毒基因的长度。
有时候科学家们没有抗体。此时显然没有任何病毒能被检验到,所以他们只想知道突变最终产生的病毒中长度最小的是多长。
输入格式
输入第一行三个整数 G,N,M(G>2,N≥G−2,M≥0),表示基因的数量,突变表的行数和抗体的种类数。
接下来的 N 行描述了突变表:每行最开始输入两个整数 a,k(2≤a≤G,k≥1);接下来输入 k 个整数 b1,b2,…,bk(0≤bi<G)。表示以下的突变方式:
a→⟨b1 b2 … bk⟩
题目保证所有的 k 之和不超过 100。2∼G−1 的整数至少在突变表中出现一次。
接下来的 M 行,每行为对抗体的描述:每行先输入一个整数 ℓ,然后是 ℓ 个整数 c1,c2,…,cℓ,描述抗体的序列。保证 ℓ 之和不超过 50。
输出格式
输出共 G−2 行,为 2∼G−1 的基因对应的答案。
如果所有从某一基因突变得到的病毒都能被抗体所检测,输出 YES
。当没有病毒来着这一基因时,同样输出 YES
(如果一个病毒不会停止突变,也属于这种情况。)。
否则输出 NO
。接着输出一个整数,表示最小的无法被检测出的基因长度。你可以假设在所有数据中这个值都小于 263。
样例
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
数据范围与提示
本题共 5 个子任务,各子任务的分值和限制如下:
子任务 1(11 分):M=0。
子任务 2(14 分):N=G−2。
子任务 3(25 分):M=1。
子任务 4(32 分):∑ℓ≤10。
子任务 5(18 分):无特殊限制。