字符串

小 $D$ 现在正在研究一种特殊的字符串：仅由 $A,B,C,D$ 四种字母组成的字符串。

对于这样的一个字符串 $S$，小 $D$ 可以用以下两种方式之一修改这个字符串：

交换 $S$ 中的相邻两个字母；
使用一种魔法。小 $D$ 共有 $m$ 种魔法，其中第 $i$ 种可以将 $S$ 中一个等于 $X_i$ 的子串（如果你不知道他是什么，可以参考 “数据规模与约定” 一节）替换为 $Y_i$。保证 $\lvert X_i\rvert=\lvert Y_i\rvert$。

小 $D$ 觉得通过修改得到不同的字符串非常有意思，于是他想要知道：对于所有这样的（即仅由 $A,B,C,D$ 四种字母组成的字符串）长度为 $n$ 的字符串 $S$，经过的字符串最多的修改序列是哪个（注意：如果一个字符串被经过了多次，他也只能被计算一次）？

你并不愿意帮助他，但是盛情难却，所以你只要帮他求出最多的那个修改序列经过了多少字符串即可。

第一行两个空格隔开的整数 $n,m$，表示字符串的长度和魔法的个数。

接下来 $m$ 行，每行两个空格隔开的字符串 $X_i,Y_i$ 表示一种魔法。保证 $X_i,Y_i$ 仅由 $A,B,C,D$ 四种字母组成。

输出一行一个整数表示答案。

2 3
A B
A C
D D

其中一种最优方案为 $AA\to AB\to BA\to BC\to CB$，这样共经过了 $5$ 个字符串。可以证明这是最优答案。

6 6
AABBC AACCB
AAAADA DAAABC
AAACA AAAAD
CABAA ABCBA
AAAAAA AABAAA
BAAAA AACAA

见 ex_string3.in/out 以及 ex_string4.in/out。

本题共 $20$ 个测试点，每个测试点 $5$ 分。

对于所有测试数据，保证 $1\le n\le 50$，$1\le m\le 100$，$1\le \lvert X_i\rvert=\lvert Y_i\rvert\le n$。注意可能有的魔法出现多次，也可能有的魔法中 $X_i=Y_i$。以下为每个测试数据的数据规模：

测试数据编号	$n\le$	$m\le$	测试数据编号	$n\le$	$m\le$
$1$	$3$	$3$	$11$	$20$	$30$
$2$	$3$	$5$	$12$	$30$	$30$
$3$	$5$	$5$	$13$	$30$	$40$
$4$	$5$	$7$	$14$	$30$	$45$
$5$	$7$	$7$	$15$	$30$	$50$
$6$	$7$	$10$	$16$	$30$	$65$
$7$	$10$	$10$	$17$	$50$	$80$
$8$	$10$	$20$	$18$	$50$	$90$
$9$	$10$	$25$	$19$	$50$	$95$
$10$	$10$	$30$	$20$	$50$	$100$

友情提醒：本题答案可能很大，甚至有可能超过 $64$ 位整数的表示范围（即 C/C++ 的 unsigned long long 以及 Pascal 的 qword）。同时，NOI 系列赛事均禁止使用非标准的 __int128（对于 C/C++ 语言），请选手注意。

子串的定义：对于字符串 $S=S_1S_2S_3\cdots S_{n-1}S_n$，$T$ 是 $S$ 的子串，当且仅当存在 $1\le l\le r\le n$，满足 $T=S_lS_{l+1}S_{l+2}\cdots S_{r-1}S_r$。

时间限制：$2\mathtt{s}$

空间限制：$512\mathtt{MB}$

NOI.AC