소개 세션 조직

Apricot Rules LLC가 조직을 개편한 뒤, 관리자 $M$명과 비관리자 $N$명으로 이루어진 대규모 새 팀이 만들어졌다. 팀원 중에는 서로 모르는 사람이 많아서 여러 번의 소개 세션을 잡아야 한다. 이미 서로 아는 팀원 쌍은 주어진다.

소개 세션은 각각 1분 길이의 시간 슬롯에서 진행된다. 첫 번째 슬롯은 오전 8시 00분에 시작해서 오전 8시 01분에 끝난다. $i$번째 슬롯은 오전 8시 00분에서 $i-1$분 뒤에 시작해서 $i$분 뒤에 끝난다. 한 슬롯에는 세션이 하나 이상 들어갈 수 있다. 팀원은 한 슬롯에 최대 하나의 세션에 배정될 수 있다. 각 세션에는 정확히 세 명이 참여한다. 반드시 관리자여야 하는 담당 관리자 $a$와, 관리자든 비관리자든 상관없는 두 명 $b$, $c$이다. 세션이 성립하려면 담당 관리자 $a$가 $b$와 $c$를 이미 알고 있어야 한다. 세션이 끝나면 $b$와 $c$도 서로를 알게 된다. $b$나 $c$ 중 한 명 또는 둘 다 관리자라면, 둘을 모두 포함하는 이후 세션의 담당 관리자는 둘 중 누구든 될 수 있다.

일부 사람 쌍에 대해, 서로 알게 되기까지 걸리는 최단 시간을 구하려고 한다. 이 과정으로는 서로 알게 될 수 없는 경우도 판별해야 한다. 세션이 시작되기 전에 이미 서로 아는 두 사람의 최단 시간은 0분이다. 쌍마다 따로 생각하므로, 가장 좋은 조직 방식은 쌍마다 달라질 수 있다.

첫 줄에는 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스는 관리자 수 $M$, 비관리자 수 $N$, 질문할 쌍의 수 $P$가 적힌 한 줄로 시작한다. 관리자는 $1$부터 $M$까지, 비관리자는 $M+1$부터 $M+N$까지 번호가 매겨진다.

이어서 길이가 $M+N$인 문자열이 $M+N$줄 주어진다. $i$번째 줄의 $j$번째 문자 $C_{i,j}$는 과정 시작 전에 팀원 $i$와 $j$가 서로 알고 있으면 Y, 아니면 N이다. 그 다음 $P$줄이 주어지며, $k$번째 줄에는 $k$번째로 질문할 쌍의 팀원 번호 두 개 $A_k$, $B_k$가 적혀 있다.

각 테스트 케이스마다 Case #x: y1 y2 y3 ⋯ yP 형식으로 한 줄을 출력한다. 여기서 $x$는 테스트 케이스 번호(1부터 시작)이다. $y_i$는 팀원 $A_k$와 $B_k$가 서로 알게 될 수 없으면 $-1$이고, 그렇지 않으면 과정이 시작된 뒤 두 사람이 서로 알게 되기까지 걸리는 최단 시간(분)이다.

• $1≤T≤100$.
• 모든 $i,j$에 대해 $C_{i,j}$는 대문자 Y 또는 N이다.
• 모든 $i,j$에 대해 $C_{i,j}=C_{j,i}$이다.
• 모든 $i$에 대해 $C_{i,i}=$ Y이다. (팀원은 자기 자신을 안다.)
• $1≤A_k$
• 모든 $k≠ℓ$에 대해 $(A_k,B_k)≠(A_ℓ,B_ℓ)$이다. (같은 쌍을 두 번 질문하지 않는다.)