A-to-Z

A-to-Z는 초등학생들이 철자 실력을 기르고 어휘를 늘리기 위해 즐겨 하는 놀이다. 놀이에는 여러 개의 단어가 주어지며, 각 단어는 플라스틱 조각에 하나씩 적혀 있다. 두 사람은 서로 두 글자(이를 $C_1$과 $C_2$라 하자)를 고른 뒤, 한 개 이상의 단어로 이루어진 수열 $W_1, W_2, \ldots, W_n$으로 두 글자를 잇는다. 이때 첫 단어 $W_1$은 $C_1$로 시작하고, 마지막 단어 $W_n$은 $C_2$로 끝나야 한다.

이웃한 두 단어 $(W_i, W_{i+1})$는 반드시 두 글자 이상 겹쳐야 한다. 단어 $X$가 단어 $Y$와 $k$글자만큼 겹친다는 것은, $X$의 마지막 $k$글자가 $Y$의 처음 $k$글자와 완전히 같다는 뜻이다. 예를 들어 아래 그림에서 a는 두 단어로 이루어진 수열 against students로 s와 이어진다.

각 수열에는 벌점이 매겨진다. 벌점은 수열에 포함된 글자 수와 같되, 겹치는 글자는 한 번만 센다. (즉, 단어들을 최대한 겹치도록 늘어놓았을 때의 전체 너비와 같다.) 벌점이 작을수록 좋다. 그림에서 against students의 벌점은 13이고, about outside ideas의 벌점은 11이다.

단어 사전이 주어질 때, 주어진 두 글자를 잇는 수열의 가능한 최소 벌점을 구하여라.

입력은 하나 이상의 테스트 케이스로 이루어진다. 각 테스트 케이스는 단어 사전과, 그 사전을 이용해 이을 글자 쌍(질의)들의 목록으로 구성된다.

각 테스트 케이스의 첫 줄에는 사전에 있는 단어의 개수를 나타내는 양의 정수 $w$가 주어진다. 이어지는 $w$개의 줄에는 각각 단어가 하나씩 주어진다. 단어는 소문자로만 이루어지며, 길이가 64를 넘지 않는다. 한 사전에는 최대 50000개의 단어가 있다.

사전 다음에는 질의의 개수 $q$가 주어지고, 이어서 $q$개의 줄이 온다. 각 질의 줄에는 두 소문자 $C_1$과 $C_2$가 공백으로 구분되어 주어진다.

입력의 끝은 정수 $w = 0$만 있는 줄로 나타내며, 이 줄은 테스트 케이스에 포함되지 않는다.

각 질의마다 한 줄씩 출력한다.

$a$를 테스트 케이스 번호(1부터 시작), $b$를 그 테스트 케이스 안에서의 질의 번호(역시 1부터 시작)라 하자.

두 글자를 잇는 수열이 존재하면 a.b p를 출력한다. 여기서 $p$는 사전 안의 모든 유효한 수열에 대한 최소 벌점이다. 두 글자를 잇는 수열이 존재하지 않으면 a.b 0을 출력한다.

비어 있지 않은 모든 수열의 벌점은 1 이상이므로, 0은 잇는 수열이 존재하지 않음을 분명하게 뜻한다. 실제 수열이 아니라 최소 벌점만 출력하면 된다.