반 딘스키의 물감 섞기

화가 지망생 반 딘스키는 그림에 쓸 물감을 직접 섞어서 만든다. 스승은 색 조합 규칙이 적힌 책과 팔레트를 주면서, 그림에 필요한 색을 하나씩 최소 횟수로 섞어 만들어 보라고 했다.

색 이름은 소문자 a부터 z까지와 숫자 0부터 9까지로만 쓴다.

규칙 하나는 한 줄에 적힌 색 이름 세 개다. yellow cyan green은 yellow와 cyan을 섞으면 green이 된다는 뜻이다. 섞는 순서는 상관없어서 반 딘스키는 yellow에 cyan을 섞는 것과 cyan에 yellow를 섞는 것을 같게 본다. 대신 책에 없는 조합은 절대 시도하지 않는다. yellow와 green을 섞은 결과가 책에 없으면 그 실험은 하지 않는다. 추론도 하지 않는다. 책에 yellow와 cyan을 섞으면 green, yellow와 magenta를 섞으면 red, red와 cyan을 섞으면 black이라고 적혀 있어도, green과 magenta를 섞으면 black이라고 짐작하지 않는다. 규칙이 책에 그대로 적혀 있어야 쓴다.

한 번 섞을 때는 재료가 되는 두 색을 한 덩이씩 써서 결과 색 한 덩이를 얻고, 쓴 두 덩이는 사라진다. 팔레트에 있는 색은 얼마든지 꺼내 쓸 수 있고 섞기 횟수에 들어가지 않는다. 반면 섞어서 만든 덩이는 한 번만 쓸 수 있어서, 같은 색이 재료로 두 번 필요하면 두 번 섞어야 한다.

정리하면 색 $c$를 만드는 비용 $\mathrm{cost}(c)$는 이렇게 정해진다. $c$가 팔레트에 있으면 $0$이다. 그렇지 않으면 $a$와 $b$를 섞어 $c$가 된다는 규칙 전체에 대한 $\mathrm{cost}(a) + \mathrm{cost}(b) + 1$의 최솟값이다. 그런 값이 하나도 없으면 $c$는 만들 수 없다.

입력의 첫 부분은 규칙 책이다. 한 줄에 색 이름 세 개가 공백으로 구분되어 주어진다. 규칙 책 다음에는 빈 줄이 하나 온다. 규칙이 하나도 없으면 입력은 빈 줄로 시작한다.

빈 줄 뒤에는 그림 작업이 하나 이상 오고, 각 작업은 두 줄로 이루어진다.

• 첫째 줄에는 처음에 팔레트에 있는 색이 공백으로 구분되어 주어진다.
• 둘째 줄에는 그림에 필요한 색이 공백으로 구분되어 주어진다.

두 줄 모두 색이 적어도 하나 있다. 규칙은 50000개 미만이고, 입력에 나오는 서로 다른 색은 1000개 미만이다.

그림 작업마다 한 줄씩 출력한다. 그 줄에는 그림에 필요한 색을 주어진 순서대로, 팔레트에서 시작해 그 색 한 덩이를 만드는 데 필요한 최소 섞기 횟수를 공백으로 구분해 출력한다. 만들 수 없는 색은 -1을 출력한다.