Problem:


Problem D: Organize Your Train

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

All freight trains travel at night, so these trains containing various types of cars are settled in
your parking lines early in the morning. Then, during the daytime, you must reorganize cars
in these trains according to the request of the railroad clients, so that every line contains the
“right” train, i.e. the right number of cars of the right types, in the right order.

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

Cars of the same type are not discriminated between each other. The cars are symmetric, so
directions of cars don’t matter either.

You can divide a train at an arbitrary position to make two sub-trains and move one of them
through an exchange line connected to the end of its side. Alternatively, you may move a whole
train as is without dividing it. Anyway, when a (sub-) train arrives at the destination parking
line and the line already has another train in it, they are coupled to form a longer train.

Your superautomatic train organization system can do these without any help of locomotive
engines. Due to the limitation of the system, trains cannot stay on exchange lines; when you
start moving a (sub-) train, it must arrive at the destination parking line before moving another
train.

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

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

Given the configurations of the train cars in the morning (arrival state) and evening (departure
state), your job is to write a program to find the optimal train reconfiguration plan.

Input

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

x y
p1 P1 q1 Q1
p2 P2 q2 Q2
.
.
.
py Py qy Qy
s0
s1
.
.
.
sx-1
t0
t1
.
.
.
tx-1

x is the number of parking lines, which are numbered from 0 to x-1. y is the number of exchange
lines. Then y lines of the exchange line data follow, each describing two ends connected by the
exchange line; pi and qi are integers between 0 and x - 1 which indicate parking line numbers,
and Pi and Qi are either "E" (East) or "W" (West) which indicate the ends of the parking lines.

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

You may assume that x does not exceed 4, the total number of cars contained in all the trains
does not exceed 10, and every parking line has sufficient length to park 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 in a line indicate the end of the input.

Output

For each dataset, output the number of moves for an optimal reconfiguration plan, in a separate
line.

Sample Input

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

Output for the Sample Input

4
2
5



Sample input:
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


Sample output:
4
2
5

Submission status: Accepted

Solution code:
def solve(file_input, x, y):
    exch1 = [] # forward - forward
    exch2 = [] # forward - reverse
    exch3 = [] # reverse - forward
    for i in range(y):
        p, P, space, q, Q = file_input.readline().rstrip()
        p = int(p)
        q = int(q)
        
        if P == 'E':
            if Q == 'W':
                exch1.append((p, q))
            else:
                exch2.append((p, q))
        else:
            if Q == 'E':
                exch1.append((q, p))
            else:
                exch3.append((q, p))
    
    fwd_init = []
    for i in range(x):
        s = file_input.readline().rstrip()
        if s == '-':
            fwd_init.append('')
        else:
            fwd_init.append(s)
    fwd_rec = {'|'.join(fwd_init): 0}
    forwrad = [fwd_init]
    
    bk_init = []
    for i in range(x):
        t = file_input.readline().rstrip()
        if t == '-':
            bk_init.append('')
        else:
            bk_init.append(t)
    bk_rec = {'|'.join(bk_init): 0}
    backward = [bk_init]
    
    for step in range(1, 4):
        tmp_forward = []
        for trains in forwrad:
            for l1, l2 in exch1:
                tmp_trains = trains[:]
                coupled = trains[l1] + trains[l2]
                for i in range(len(coupled) + 1):
                    tmp_trains[l1] = coupled[:i]
                    tmp_trains[l2] = coupled[i:]
                    tmp_state = '|'.join(tmp_trains)
                    if tmp_state not in fwd_rec:
                        if tmp_state in bk_rec:
                            return bk_rec[tmp_state] + step
                        fwd_rec[tmp_state] = step
                        tmp_forward.append(tmp_trains[:])
            for l1, l2 in exch2:
                tmp_trains = trains[:]
                coupled = trains[l1] + trains[l2][::-1]
                for i in range(len(coupled) + 1):
                    tmp_trains[l1] = coupled[:i]
                    tmp_trains[l2] = coupled[i:][::-1]
                    tmp_state = '|'.join(tmp_trains)
                    if tmp_state not in fwd_rec:
                        if tmp_state in bk_rec:
                            return bk_rec[tmp_state] + step
                        fwd_rec[tmp_state] = step
                        tmp_forward.append(tmp_trains[:])
            for l1, l2 in exch3:
                tmp_trains = trains[:]
                coupled = trains[l1][::-1] + trains[l2]
                for i in range(len(coupled) + 1):
                    tmp_trains[l1] = coupled[:i][::-1]
                    tmp_trains[l2] = coupled[i:]
                    tmp_state = '|'.join(tmp_trains)
                    if tmp_state not in fwd_rec:
                        if tmp_state in bk_rec:
                            return bk_rec[tmp_state] + step
                        fwd_rec[tmp_state] = step
                        tmp_forward.append(tmp_trains[:])
        forwrad = tmp_forward
        
        if step == 3:
            return 6
        
        tmp_backward = []
        for trains in backward:
            for l1, l2 in exch1:
                tmp_trains = trains[:]
                coupled = trains[l1] + trains[l2]
                for i in range(len(coupled) + 1):
                    tmp_trains[l1] = coupled[:i]
                    tmp_trains[l2] = coupled[i:]
                    tmp_state = '|'.join(tmp_trains)
                    if tmp_state not in bk_rec:
                        if tmp_state in fwd_rec:
                            return fwd_rec[tmp_state] + step
                        bk_rec[tmp_state] = step
                        tmp_backward.append(tmp_trains[:])
            for l1, l2 in exch2:
                tmp_trains = trains[:]
                coupled = trains[l1] + trains[l2][::-1]
                for i in range(len(coupled) + 1):
                    tmp_trains[l1] = coupled[:i]
                    tmp_trains[l2] = coupled[i:][::-1]
                    tmp_state = '|'.join(tmp_trains)
                    if tmp_state not in bk_rec:
                        if tmp_state in fwd_rec:
                            return fwd_rec[tmp_state] + step
                        bk_rec[tmp_state] = step
                        tmp_backward.append(tmp_trains[:])
            for l1, l2 in exch3:
                tmp_trains = trains[:]
                coupled = trains[l1][::-1] + trains[l2]
                for i in range(len(coupled) + 1):
                    tmp_trains[l1] = coupled[:i][::-1]
                    tmp_trains[l2] = coupled[i:]
                    tmp_state = '|'.join(tmp_trains)
                    if tmp_state not in bk_rec:
                        if tmp_state in fwd_rec:
                            return fwd_rec[tmp_state] + step
                        bk_rec[tmp_state] = step
                        tmp_backward.append(tmp_trains[:])
        backward = tmp_backward

def main():
    from sys import stdin
    f_i = stdin
    
    while True:
        x, y = map(int, f_i.readline().split())
        
        if x == 0:
            break
        
        print(solve(f_i, x, y))

main()