sed 이용

sed는 입력으로 주어지는 문자열에 등장하는 문자열 α를 다른 문자열 β로 바꾸는데 사용되는 리눅스 유틸이다. 여기서 입력으로 주어지는 문자열은 파일의 각 한 줄이다. sed는 다음과 같은 2가지 과정을 거친다.

1. 입력 문자열에서 겹치지 않는 α를 표시한다. 이때, α가 서로 겹칠 수는 있다. 만약, 겹치지 않게 선택하는 경우가 여러 가지 있을 때는 가장 왼쪽 것을 선택한다.
2. 위에서 표시한 모둔 문자열 α를 문자열 β로 바꾼다. 나머지 문자는 바꾸지 않고 그대로 놔둔다.

예를 들어, α가 "aa"이고, β가 "bca", 입력 문자열이 "aaxaaa"라면 sed를 실행한 결과는 "bcaxbcaa"가 된다. ("aaxbcaa", "bcaxabca"는 될 수 없다) 이 결과 "bcaxbcaa"를 가지고 다시 sed를 실행하면 결과는 "bcaxbcbca"가 된다.

문자열을 바꾸는 규칙의 쌍 (αi, βi) (i = 1,2,...,n), 초기 문자열 γ, 최종 문자열 δ가 주어진다. 이때, sed를 이용해서 γ를 δ로 바꿀 때, 문자열 바꾸는 회수의 최솟값을 구하려고 한다.

하나의 규칙(αi, βi)은 위에서 설명한 것 같이, 입력 문자열에서 겹치지 않는 모든 부분 문자열 αi를 βi로 동시에 바꾸는 것을 의미한다.

한 규칙(αi, βi)을 여러 번 사용해도 되고, 사용하지 않아도 된다.

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

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

n은 문자열을 바꾸는 규칙의 쌍의 개수이다. αi와 βi는 공백으로 구분되어 있으며, 1 ≤ |αi| < |βi| ≤ 10을 만족한다. (|s|는 문자열 s의 길이) 모든 i≠j에 대해서 αi≠αj이며, n ≤ 10, 1 ≤ |γ| < |δ| ≤ 10 이다. 모든 문자열을 알파벳 소문자로만 이루어져 있고, 입력의 마지막 줄에는 0이 하나 주어진다.

각 테스트 케이스에 대해서, γ를 δ로 바꿀 때 필요한 문자열 바꾸는 회수의 최솟값을 출력한다. 만약 γ를 δ로 바꿀 수 없다면, -1을 출력한다.