游戏设计师 题目描述

 你是游戏设计师，你要设计所有长度为K的字符串，每个字符是‘A’或‘B’或‘C’或‘D’，显然共有4K个不同的字符串，你要给每个字符串都分配一种颜色，不同的字符串可以分配相同的颜色，颜色分配过程是由你来决定的。

 奶牛Bessie是这个游戏的玩家，首先Bessie会输入一个长度是K的字符串S（每个字符也是‘A’或‘B’或‘C’或‘D’），然后Bessie每一步操作是如下两种选择之一：

1、 交换当前的字符串S的相邻的两个字符。注意，第一个字符和最后一个字符不算相邻，即S不能看成一个环。

2、把当前的字符串S中的某个子串b[i]，替换成子串c[i]。其中b数组和c数组是作为输入数据给出来的。

如果Bessie能够通过上面的操作，使得从字符串S出发，通过若干次操作之后，变成了字符串T（T和S是不同的字符串），且字符串T和字符串S是相同颜色的，那么Bessie就会胜利了。

作为游戏设计师的你，你的目的是想让Bessie永远都不可能胜利，也就是说无论Bessie输入的字符串S是什么，都不可能胜利。显然，这与你对4K个不同的字符串如何分配颜色是非常重要的。现在的问题是，你至少需要多少种不同的颜色，才能使得Bessie永远不可能胜利。

输入格式

  第一行，两个整数K和N。 1 <= K <= 30， 1 <= N <= 50。

  第二行，N个字符串，空格分开，第i个字符表示b[i]。每个字符也是A’或‘B’或‘C’或‘D’。

  第三行， N个字符串，空格分开，第i个字符表示c[i]。每个字符也是A’或‘B’或‘C’或‘D’。

输出格式

一个整数。

输入样例 1

1 1 A B 输出样例 1

2 输入样例 2

2 3 A A D B C D 输出样例 2

5 输入样例 3

2 3 B C D C D B 输出样例 3

9 提示

【样例1解释】

要使得Bessie不可能赢，至少需要2种不同的颜色，因为假如只有一种颜色，那么字符串“A”、“B”、“C”、“D”都是相同颜色，那么如果Bessie一开始输入的字符串是“A”，那么通过一次替换操作之后，就变成字符串“B”了，由于字符串“A”和字符串“B”颜色相同，所以Bessie就赢得游戏了。我们也能证明，只要2种不同颜色就足够了，因为如果你把字符串“A”和字符串“C”设置为颜色1，而把字符串“B”和字符串“D”设置成为颜色2，那么无论Bessie输入什么字符串（当然，Bessie输入的字符串长度是1，即“A”或“B”或“C”或“D”），都永远不可能胜利,由于你是游戏设计师，你完全可以这样分配颜色。