Problem2740--Bovine Genomics[USACO-2017-USopen-B]

2740: Bovine Genomics[USACO-2017-USopen-B]

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 0  Solved: 0
[Status] [Submit] [Creator:]

Description

Farmer John有N头带有斑点的奶牛和N头没有斑点的奶牛。刚刚结束了牛科遗传学课程,他确信奶牛斑点是由牛基因组织中的一个位置突变引起的。
FJ付出了巨大的代价对奶牛的基因进行了测序,每个基因组都是一个长度为M的字符串,字符串由A、C、G、T四个字母组成,他用如下的表格形式列举出所有奶牛的基因组。
下面显示了N=3时的表格:
Positions:    1 2 3 4 5 6 7 ... M
Spotty Cow 1: A A T C C C A ... T
Spotty Cow 2: G A T T G C A ... A
Spotty Cow 3: G G T C G C A ... A
Plain  Cow 1: A C T C C C A ... G
Plain  Cow 2: A C T C G C A ... T
Plain  Cow 3: A C T T C C A ... T
仔细观察这张表,FJ猜测位置2是基因组中可能影响斑点的潜在位置,也就是说,通过查看这个位置上的字母,FJ可以预测出这个奶牛是有斑点的还是没有斑点的(上述的表格中,这个位置是A或G,表示是有斑点,C表示没有斑点,T无关紧要,因为在位置2上没有出现过字母T)。位置1不足以预测斑点,因为这个位置上的A可能表示有斑点的牛或是无斑点的牛。
给定FJ的奶牛的基因组,请确定出可能预测出奶牛斑点的基因的位置的编号

Input

第一行,两个整数,分别表示N和M。(N,M≤100)
接下来N行,每行M个字符,表示N头有斑点的奶牛的基因组
最后N行,每行M个字符,表示N头没有斑点的奶牛的基因组

Output

输出一个整数,计算出可能预测出斑点的基因位置的数量(0到M之间的整数)。
如果通过观察基因组中的这个位置,能够在FJ的所有奶牛中准确的预测斑点的特征,那么这个位置就是可能预测出斑点的基因位置。

Sample Input Copy

3 8
AATCCCAT
GATTGCAA
GGTCGCAA
ACTCCCAG
ACTCGCAT
ACTTCCAT

Sample Output Copy

1

Source/Category

 USACO 2017 level4