친구

세상에는 1부터 N까지 번호가 매겨진 N명의 사람이 있다. i번째 사람에게는 영문 대문자로 이루어진 서로 다른 이름 $S_{i}$가 있다.

두 사람 각각의 이름에 적어도 한 번 등장하는 어떤 글자가 있을 때, 그리고 그럴 때에만 두 사람은 친구이다. 그러한 글자가 두 이름에서 같은 위치에 있을 필요는 없다. 결국 우정에는 공통점이 필요하다!

사람 A와 사람 B 사이의 길이가 n인 친구 관계 사슬은 사람들의 수열 $X_{1}$, $X_{2}$, ..., $X_{n}$이며, $X_{1}$ = A, $X_{n}$ = B이고 i=1부터 n-1까지 $X_{i}$와 $X_{i+1}$가 친구인 것을 말한다. 임의의 두 사람 사이에는 친구 관계 사슬이 없거나 여러 개 있을 수 있음에 유의하라.

주어진 Q개의 사람 쌍 각각에 대해, 두 사람 사이의 가장 짧은 친구 관계 사슬의 길이를 구할 수 있는가? 어떤 쌍 사이에 친구 관계 사슬이 없다면 -1을 출력한다.

제한

시간 제한: 40초. 메모리 제한: 1 GB. 1 ≤ T ≤ 100. 1 ≤ Q ≤ 5 × $10^{4}$. 모든 i에 대해 $S_{i}$는 영문 대문자로 구성된다. 모든 i에 대해 1 ≤ $S_{i}$의 길이 ≤ 20. 모든 $S_{i}$는 서로 다르다. 모든 i에 대해 1 ≤ $X_{i}$ <$Y_{i}$ ≤ N.

테스트 세트 1

2 ≤ N ≤ 100.

테스트 세트 2

최대 10개의 케이스에서 $10^{3}$ < N ≤ 5 × $10^{4}$. 그 밖의 모든 케이스에서 2 ≤ N ≤ $10^{3}$.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 줄에는 두 정수 N과 Q가 주어진다. 둘째 줄에는 사람들의 이름인 N개의 문자열이 주어진다. i번째 문자열은(1부터 시작) $S_{i}$이다. 이어지는 Q개의 줄에는 쿼리가 주어진다. 이 중 i번째 줄에는 이름 목록에 있는 한 사람 쌍의 인덱스(1부터 세기 시작)인 두 정수 $X_{i}$와 $Y_{i}$가 주어진다.

각 테스트 케이스마다 Case #x: y를 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며(1부터 시작), y는 Q개 쿼리의 답을 순서대로 공백으로 구분한 목록이다.

예제 케이스 #1에는 두 개의 쿼리가 있다.

• 첫 번째 쿼리에서 LIZZIE와 KEVIN는 친구이다(두 이름에 글자 E가 공통으로 있기 때문이다). 따라서 가장 짧은 친구 관계 사슬의 길이는 2이다.

• 두 번째 쿼리에서 LIZZIE와 BOHDAN는 친구가 아니지만, 가능한 가장 짧은 친구 관계 사슬이 두 개 있다(KEVIN 또는 LALIT를 거친다). 따라서 가장 짧은 친구 관계 사슬의 길이는 3이다. 다른 친구 관계 사슬도 있지만 더 길다는 점에 유의하라.

예제 케이스 #2에는 두 개의 쿼리가 있다.

• 첫 번째 쿼리에서 KICK와 START는 친구 관계 사슬로 연결되어 있지 않다.

• 두 번째 쿼리는 첫 번째 쿼리와 같다. 쿼리가 서로 다르다고 보장되지 않음에 유의하라.