sed 사용하기

sed는 입력으로 주어진 문자열에서 문자열 $\alpha$를 다른 문자열 $\beta$로 바꾸는 데 사용되는 리눅스 유틸리티이다. 여기서 입력으로 주어지는 문자열은 파일의 한 줄이다. sed는 다음 두 단계를 수행한다.

1. 입력 문자열에서 서로 겹치지 않는 $\alpha$의 등장을 표시한다. (원래 문자열에서 $\alpha$끼리 겹칠 수는 있지만, 표시하는 것들은 서로 겹치면 안 된다.) 서로 겹치지 않게 고르는 방법이 여러 가지이면 가장 왼쪽에 있는 것들을 고른다.
2. 표시한 모든 $\alpha$를 동시에 $\beta$로 바꾼다. 나머지 문자는 그대로 둔다.

예를 들어 $\alpha$가 aa, $\beta$가 bca, 입력 문자열이 aaxaaa이면 sed를 실행한 결과는 bcaxbcaa이다. (aaxbcaa나 bcaxabca는 될 수 없다.) 이 결과 bcaxbcaa에 sed를 다시 실행하면 bcaxbcbca가 된다.

문자열을 바꾸는 규칙 $n$개 $(\alpha_i, \beta_i)$ ($i = 1, 2, \ldots, n$), 초기 문자열 $\gamma$, 최종 문자열 $\delta$가 주어진다. sed를 이용해 $\gamma$를 $\delta$로 바꿀 때 필요한 문자열 바꾸기 연산 횟수의 최솟값을 구하려고 한다.

하나의 규칙 $(\alpha_i, \beta_i)$는 위에서 설명한 대로 현재 문자열에서 서로 겹치지 않는(가장 왼쪽) $\alpha_i$의 모든 등장을 동시에 $\beta_i$로 바꾸는 것을 뜻하며, 이것이 한 번의 연산이다. 각 규칙은 여러 번 사용해도 되고 사용하지 않아도 된다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 형식은 다음과 같다.

n
α1 β1
α2 β2
...
αn βn
γ
δ

$n$은 문자열 바꾸기 규칙의 개수이다. $\alpha_i$와 $\beta_i$는 공백으로 구분되며 $1 \le |\alpha_i| < |\beta_i| \le 10$을 만족한다. ($|s|$는 문자열 $s$의 길이) 모든 $i \ne j$에 대해 $\alpha_i \ne \alpha_j$이고, $n \le 10$, $1 \le |\gamma| < |\delta| \le 10$이다. 모든 문자열은 알파벳 소문자로만 이루어져 있으며, 입력의 마지막 줄에는 $0$이 하나 주어진다.

각 테스트 케이스에 대해 $\gamma$를 $\delta$로 바꾸는 데 필요한 문자열 바꾸기 연산 횟수의 최솟값을 출력한다. 만약 $\gamma$를 $\delta$로 바꿀 수 없다면 $-1$을 출력한다.