열차 재배치

도쿄 서쪽에 자리한 유서 깊은 하치오지 철도역에는 여러 개의 주차선이 있고, 매일 많은 화물열차가 오간다.

모든 화물열차는 밤에 이동하므로, 다양한 종류의 차량으로 이루어진 열차들은 이른 아침 주차선에 놓여 있다. 그러면 낮 동안 고객의 요청에 따라 열차 안의 차량들을 재배치하여, 모든 선이 "올바른" 열차 — 올바른 종류의 차량이 올바른 개수만큼 올바른 순서로 놓인 열차 — 를 갖도록 해야 한다.

그림 7: 주차선과 교환선.

그림 7처럼 모든 주차선은 동서 방향으로 뻗어 있다. 주차선들을 잇는 교환선이 있으며, 이를 통해 차량을 옮길 수 있다. 교환선은 서로 다른 두 주차선의 양 끝을 잇는다. 한 주차선의 한 끝이 다른 여러 선의 끝과 이어질 수 있고, 교환선이 어떤 주차선의 동쪽 끝과 다른 주차선의 서쪽 끝을 이을 수도 있음에 유의하라.

같은 종류의 차량은 서로 구별하지 않는다. 차량은 대칭이므로 차량의 방향도 중요하지 않다.

열차를 임의의 위치에서 둘로 나누어 두 부분열차를 만들고, 그중 한 쪽 끝에 이어진 교환선을 통해 그 쪽 부분열차를 옮길 수 있다. 또는 나누지 않고 열차 전체를 그대로 옮길 수도 있다. 어느 경우든, 부분열차가 목적지 주차선에 도착했을 때 그 선에 이미 다른 열차가 있으면, 둘은 이어져 더 긴 열차가 된다.

당신의 초자동 열차 정리 시스템은 기관차 없이도 이 일을 해낸다. 시스템의 제약상 열차는 교환선 위에 머물 수 없다. 즉 한 부분열차를 옮기기 시작하면, 다른 열차를 옮기기 전에 그 부분열차가 목적지 주차선에 도착해야 한다.

이하에서 하나의 글자는 차량의 종류를 나타내고, 열차는 글자들의 나열로 표현한다. 예를 들어 그림 8에서, 0번 선에 열차 "aabbccdee"가 있고 나머지 선에는 열차가 없는 초기 상태에서 시작해, 그림에 나온 네 번의 이동으로 2번 선에 "bbaadeecc"를 만들 수 있다.

그림 8: 이동 순서의 예.

비용을 줄이기 위해 상사는 부분열차 이동 횟수를 최소로 하고 싶어 한다. 예를 들어 그림 8의 경우 이동 횟수는 4이며, 이것이 최솟값이다.

아침(도착 상태)과 저녁(출발 상태)의 차량 배치가 주어질 때, 최적의 열차 재배치 계획을 찾는 프로그램을 작성하라.

입력은 하나 이상의 데이터셋으로 이루어진다. 각 데이터셋의 형식은 다음과 같다.

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

x는 주차선의 수로, $0$부터 $x-1$까지 번호가 매겨진다. y는 교환선의 수이다. 이어서 교환선 데이터가 y줄 나오며, 각 줄은 그 교환선이 잇는 두 끝을 두 개의 토큰으로 나타낸다. 각 토큰은 주차선 번호($0$ 이상 $x-1$ 이하의 정수) 바로 뒤에 E(동쪽) 또는 W(서쪽)를 붙인 것으로, 그 주차선의 한 끝을 나타낸다.

그다음 도착(초기) 배치 $s_0, \dots, s_{x-1}$이 x줄, 이어서 출발(목표) 배치 $t_0, \dots, t_{x-1}$이 x줄 나온다. 각 줄에는 해당 주차선 위 열차의 차량 종류를 서쪽에서 동쪽 순서로 나타낸 소문자 a, b, ..., z가 하나 이상 들어 있거나, 주차선이 비어 있으면 "-" 하나가 들어 있다.

$x$는 $4$를 넘지 않고, 모든 열차의 차량 총수는 $10$을 넘지 않으며, 모든 주차선은 차량을 모두 수용할 만큼 충분히 길다고 가정해도 된다. 또한 각 데이터셋에는 해가 적어도 하나 있으며, 이동 횟수의 최솟값은 $1$ 이상 $6$ 이하라고 가정해도 된다.

한 줄에 두 개의 $0$이 오면 입력의 끝을 뜻한다.

각 데이터셋에 대해, 최적 재배치 계획의 이동 횟수를 한 줄에 하나씩 출력한다.