题目描述

Berland 的字母表由前 $N$ 个小写拉丁字母组成，即 a、b、……。

当地人在短信中使用一种简单缩写：一个单词只保留首字母和末字母。题目给定的词典恰好只包含长度为 $2$ 的单词，因此每个单词本身就可以看成一个有序字母对。

Bergamot 公司准备设计一种新手机。手机键盘共有若干个按键，每个按键上放一个或多个字母，并且每个字母必须且只能出现在一个按键上。

输入一个两字母单词 xy 时，用户依次按下：

1. 包含字母 x 的按键；
2. 包含字母 y 的按键。

如果词典中任意两个不同单词都不会产生完全相同的“两个按键序列”，则称这种字母放置方案是正确的。

你的任务是求出使方案正确所需的最少按键数。不需要输出具体的字母分组方案。

输入格式

第一行包含两个整数 $N,M$：

$1\le N\le13$，$0\le M\le50$。

接下来 $M$ 行，每行一个长度恰好为 $2$ 的小写字符串，表示词典中的一个单词。只会使用字母表中的前 $N$ 个字母，且所有单词互不相同。

输出格式

输出一个整数 $K$，表示最少需要的按键数。

样例 1

3 3
ab
aa
bc

一种合法输出为：

2

样例 2

4 2
ab
cd

一种合法输出为：

2

样例 3

5 4
aa
bb
cc
dd

一种合法输出为：

4