접미사 치환 문법

컴퓨터 프로그래머라면 정규 표현식과 문맥 자유 문법에 대해 들어본 적이 있을 것이다. 이들은 작은 알파벳 위에서 문자열의 집합, 즉 형식 언어를 생성하는 강력한 방법이다. 트리 인접 문법, 문맥 민감 문법, 제한 없는 문법처럼 언어를 생성하는 다른 방법도 있다. 이 문제는 언어를 생성하는 새로운 방법인 접미사 치환 문법을 사용한다.

접미사 치환 문법은 시작 문자열 S와 접미사 치환 규칙의 집합으로 이루어진다. 각 규칙은 X → Y 형태이며, X와 Y는 길이가 같은 영숫자 문자열이다. 이 규칙은 현재 문자열의 접미사(가장 오른쪽 문자들)가 X이면, 그 접미사를 Y로 바꿀 수 있다는 뜻이다. 규칙은 임의의 횟수만큼 적용할 수 있다.

예를 들어 규칙이 A → B, AB → BA, AA → CC, CC → BB 네 개 있다고 하자. 문자열 AA는 규칙 세 번으로 BB가 된다. AA → AB (A → B 사용), 그다음 AB → BA, 마지막으로 BA → BB (다시 A → B 사용)이다. 두 번만 적용해도 된다. AA → CC, 그다음 CC → BB이다.

접미사 치환 문법과 문자열 T를 입력받아, 시작 문자열 S를 T로 바꿀 수 있는지 판별하는 프로그램을 작성하라. 바꿀 수 있다면 필요한 규칙 적용 횟수의 최솟값도 구하라.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 케이스는 길이가 같은 영숫자 문자열 S와 T(각각 1자 이상 20자 이하, 공백으로 구분)와 규칙의 개수 NR(0 이상 100 이하)이 적힌 줄로 시작한다. 이어지는 NR개의 줄에는 각각 길이가 같은 영숫자 문자열 X와 Y(각각 1자 이상 20자 이하, 공백으로 구분)가 주어지며, 이는 X → Y가 문법의 규칙이라는 뜻이다. 문자열은 대소문자를 구분한다. 마지막 테스트 케이스 다음 줄에는 마침표(.) 하나만 적혀 있다.

각 테스트 케이스마다 케이스 번호(1부터 시작)와 S를 T로 바꾸는 데 필요한 규칙 적용 횟수의 최솟값을 출력한다. 변환이 불가능하면 No solution을 출력한다. 출력 형식을 정확히 따른다.