在东京西部的八王子火车站，有几条停车线，每天都有许多货运列车往来。

所有的货运列车都在夜间运行，因此这些装载着各种类型车厢的列车在清晨时分停放在停车线上。白天，你必须根据铁路客户的要求重新编组这些列车，使得每条线上都停放着“正确”的列车，即车厢类型和顺序都符合要求的列车。

如图 7 所示，所有的停车线都沿东西方向延伸。停车线之间有交换线，你可以通过交换线移动车厢。一条交换线连接两条不同停车线的末端。注意，一条停车线的末端可以连接到其他多条线的末端。此外，一条交换线也可以连接一条停车线的东端和另一条停车线的西端。

图 7：停车线与交换线

相同类型的车厢之间没有区别。车厢是对称的，因此车厢的方向也不重要。

你可以将一列火车在任意位置拆分成两列子列车，并将其中一列通过连接其所在端点的交换线移动。或者，你也可以在不拆分的情况下移动整列火车。无论如何，当一列（子）列车到达目标停车线时，如果该线上已经有另一列火车，它们会耦合在一起形成更长的列车。

你的全自动列车编组系统无需任何机车引擎即可完成这些操作。由于系统的限制，列车不能停留在交换线上；当你开始移动一列（子）列车时，它必须在移动下一列火车之前到达目标停车线。

在下文中，字母代表车厢类型，列车表示为字母序列。例如在图 8 中，从初始状态（0 号线上有列车 “aabbccdee”，其他线上没有列车）出发，你可以通过图中所示的四次移动，在 2 号线上编组出 “bbaadeecc”。

图 8：移动序列示例

为了降低成本，你的老板希望最小化（子）列车的移动次数。例如，在图 8 的情况下，移动次数为 4，这是最小值。

给定清晨（到达状态）和傍晚（出发状态）的列车车厢配置，你的任务是编写一个程序来寻找最优的列车重组计划。

输入格式

输入包含一个或多个数据集。每个数据集的格式如下：

$x$ $y$ $p_1 P_1$ $q_1 Q_1$ $p_2 P_2$ $q_2 Q_2$ $\vdots$ $p_y P_y$ $q_y Q_y$ $s_0$ $s_1$ $\vdots$ $s_{x-1}$ $t_0$ $t_1$ $\vdots$ $t_{x-1}$

$x$ 是停车线的数量，编号从 $0$ 到 $x-1$。$y$ 是交换线的数量。接下来是 $y$ 行交换线数据，每行描述由交换线连接的两个端点；$p_i$ 和 $q_i$ 是 $0$ 到 $x-1$ 之间的整数，表示停车线编号，$P_i$ 和 $Q_i$ 为 “E”（东）或 “W”（西），表示停车线的端点。

随后是 $x$ 行到达（初始）配置数据 $s_0, \dots, s_{x-1}$，以及 $x$ 行出发（目标）配置数据 $t_0, \dots, t_{x-1}$。这些行中的每一行都包含一个或多个小写字母 “a”, “b”, $\dots$, “z”，表示对应停车线上列车的车厢类型（按从西到东的顺序），或者用单个 “-” 表示停车线为空。

你可以假设 $x$ 不超过 4，所有列车包含的车厢总数不超过 10，且每条停车线都有足够的长度停放所有车厢。

你还可以假设每个数据集至少有一个解，且最小移动次数在 1 到 6 之间（含边界）。

输入以一行两个零结束。

输出格式

对于每个数据集，在单独的一行中输出最优重组计划的移动次数。

样例

输入 1

3 5
0W 1W
0W 2W
0W 2E
0E 1E
1E 2E
aabbccdee
-
-
-
-
bbaadeecc
3 3
0E 1W
1E 2W
2E 0W
aabb
bbcc
aa
bbbb
cc
aaaa
3 4
0E 1W
0E 2E
1E 2W
2E 0W
ababab
-
-
aaabbb
-
-
0 0

输出 1

4
2
5