Organize Your Train

In the good old Hachioji railroad station in the west of Tokyo, there are several parking lines, and many freight trains come and go every day.

All freight trains travel at night, so trains carrying various types of cars are settled on the parking lines early in the morning. Then, during the day, you must reorganize the cars in these trains according to the clients' requests, so that every line holds the "right" train: the right number of cars of the right types, in the right order.

Figure 7: Parking lines and exchange lines.

As shown in Figure 7, all parking lines run East-West. There are exchange lines connecting them, through which you can move cars. An exchange line connects two ends of different parking lines. Note that one end of a parking line can be connected to many ends of other lines, and that an exchange line may connect the East end of one parking line to the West end of another.

Cars of the same type are not distinguished from one another. The cars are symmetric, so the direction of a car does not matter either.

You may divide a train at an arbitrary position into two sub-trains and move one of them through an exchange line connected to the end on its side. Alternatively, you may move a whole train as is, without dividing it. In either case, when a (sub-)train arrives at the destination parking line and that line already holds another train, they are coupled into a longer train.

Your super-automatic train organization system does all of this without any locomotive engines. Due to a limitation of the system, trains cannot stay on exchange lines; once you start moving a (sub-)train, it must arrive at the destination parking line before you move another train.

In what follows, a letter represents a car type and a train is written as a sequence of letters. For example, in Figure 8, starting from a state with the train "aabbccdee" on line 0 and no trains on the other lines, you can make "bbaadeecc" on line 2 with the four moves shown in the figure.

Figure 8: An example movement sequence.

To cut costs, your boss wants to minimize the number of (sub-)train moves. For example, in the case of Figure 8 the number of moves is 4, and this is the minimum.

Given the configuration of the train cars in the morning (the arrival state) and in the evening (the departure state), write a program that finds the optimal train reconfiguration plan.

The input consists of one or more datasets. A dataset has the following format.

x y
p1P1 q1Q1
p2P2 q2Q2
...
pyPy qyQy
s0
s1
...
sx-1
t0
t1
...
tx-1

x is the number of parking lines, numbered from 0 to x-1. y is the number of exchange lines. Then y lines of exchange-line data follow, each describing the two ends connected by that exchange line as two tokens. Each token is a parking line number (an integer between 0 and x-1) immediately followed by either E (East) or W (West), indicating one end of that parking line.

Then x lines of the arrival (initial) configuration s0, ..., sx-1 follow, and then x lines of the departure (target) configuration t0, ..., tx-1. Each of these lines contains one or more lowercase letters a, b, ..., z giving the car types of the train on the corresponding parking line, in west-to-east order, or a single "-" when the parking line is empty.

You may assume that x does not exceed 4, that the total number of cars over all trains does not exceed 10, and that every parking line is long enough to hold all the cars. You may also assume that each dataset has at least one solution and that the minimum number of moves is between one and six, inclusive.

Two zeros on a line indicate the end of the input.

For each dataset, output the number of moves of an optimal reconfiguration plan on its own line.