소개 세션 구성

After Apricot Rules LLC에서 조직 개편이 이루어져, $\mathbf{M}$명의 관리자와 $\mathbf{N}$명의 비관리자로 이루어진 새로운 대규모 팀이 구성되었다. 팀 내에서 서로 모르는 사람이 많으므로 여러 소개 세션을 계획하려 한다. 어떤 구성원 쌍이 이미 서로 아는지는 정확히 알고 있다.

소개 세션은 각각 $1$분 동안 진행되는 시간대로 구성된다. 첫 번째 시간대는 8:00 AM에 시작하여 8:01 AM에 끝난다. $i$번째 시간대는 8:00 AM에서 $i-1$분 후에 시작하여 8:00 AM에서 $i$분 후에 끝난다. 각 시간대에는 하나 이상의 소개 세션이 열릴 수 있다. 한 팀 구성원은 각 시간대에 최대 하나의 소개 세션에 배정될 수 있다. 각 소개 세션에는 정확히 세 명의 구성원이 있어야 한다. 즉, 관리자여야 하는 담당 관리자 $a$와, 관리자 또는 비관리자일 수 있는 다른 두 명 $b$ 및 $c$이다. 세션을 계획하려면 담당 관리자 $a$가 $b$와 $c$를 이미 알고 있어야 한다. 소개 세션이 끝나면 $b$와 $c$도 서로 아는 것으로 간주한다. $b$와 $c$ 중 하나 또는 둘 다가 관리자라면, 두 사람이 모두 참여하는 향후 소개 세션에서 그중 어느 쪽이든 담당 관리자가 될 수 있다.

팀 내 일부 사람 쌍에 대해, 그들이 마침내 서로 알게 되는 데 필요한 최단 시간이 얼마인지, 또는 설명한 과정을 통해서는 그렇게 되는 것이 불가능한지를 알고자 한다. 두 사람이 소개 세션이 열리기 전부터 서로 안다면 그 최단 시간을 $0$분으로 정의한다.

여러 사람 쌍에 관심이 있기는 하지만 각 상황은 독립적으로 고려한다. 즉, 각 쌍의 최소 시간은 오직 그 쌍만을 위한 특정한 소개 구성에 따라 달라질 수 있다.

제한

메모리 제한: 1 GB. $1 \le \mathbf{T} \le 100$. 모든 $i, j$에 대해 $\mathbf{C_{i,j}}$은 대문자 Y 또는 대문자 N이다. 모든 $i, j$에 대해 $\mathbf{C_{i,j}}$ = $\mathbf{C_{j,i}}$이다. 모든 $i$에 대해 $\mathbf{C_{i,i}}$ = Y이다. (팀 구성원은 자기 자신을 안다.) 모든 $k$에 대해 $1 \le \mathbf{A_k} \lt \mathbf{B_k} \le \mathbf{M} + \mathbf{N}$이다. 모든 $k ≠ \ell$에 대해 $(\mathbf{A_k}, \mathbf{B_k}) \neq (\mathbf{A_\ell}, \mathbf{B_\ell})$이다. (어떤 팀 구성원 쌍도 두 번 질의되지 않는다.)

테스트 세트 1 (Visible Verdict)

시간 제한: 20초. $1 \le \mathbf{M} \le 3$. $1 \le \mathbf{N} \le 2$. $1 \le \mathbf{P} \le 3$.

테스트 세트 2 (Hidden Verdict)

시간 제한: 40초. $1 \le \mathbf{M} \le 50$. $1 \le \mathbf{N} \le 50$. $1 \le \mathbf{P} \le 100$.

입력의 첫 번째 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다. 각 테스트 케이스는 세 정수 $\mathbf{M}$, $\mathbf{N}$, $\mathbf{P}$이 포함된 한 줄로 시작하며, 각각 새 팀의 관리자 수, 새 팀의 비관리자 수, 질의할 팀 구성원 쌍의 수를 나타낸다. 관리자는 1부터 $\mathbf{M}$까지, 비관리자는 $\mathbf{M} + 1$부터 $\mathbf{M} + \mathbf{N}$까지 번호가 매겨진다. 그다음 각각 $\mathbf{M} + \mathbf{N}$개의 문자를 포함하는 $\mathbf{M} + \mathbf{N}$개의 줄이 주어진다. 이 줄들 중 i번째 줄의 j번째 문자 $\mathbf{C_{i,j}}$는 소개 과정이 시작되기 전에 팀 구성원 $i$와 $j$가 서로 안다면 Y이고, 그렇지 않다면 N이다. 그다음 $\mathbf{P}$개의 줄이 더 주어지며, 그중 $k$번째 줄에는 각각 정수 $\mathbf{A_k}$와 $\mathbf{B_k}$의 쌍이 주어진다. 이는 관심 있는 $k$번째 쌍을 이루는 팀 구성원의 번호를 나타낸다.

각 테스트 케이스마다 Case #$x$: $y_1\ y_2\ y_3 \cdots y_\mathbf{P}$을 포함하는 한 줄을 출력한다. 여기서 $x$은 테스트 케이스 번호이며, 1부터 시작한다. $y_i$은 팀 구성원 $\mathbf{A_k}$와 $\mathbf{B_k}$가 서로 알게 될 수 없다면 $-1$이고, 그렇지 않다면 과정이 시작된 후 두 사람이 서로 알게 될 때까지 걸리는 최단 시간(분 단위)이다.

예제 케이스 #1에서 관리자 $1$은 처음부터 다른 모든 사람을 알고 있으며, 그 외에는 서로 아는 사람 쌍이 없다. 따라서 관리자 $1$을 포함하는 모든 쌍은 처음부터 서로 알기 때문에 결과가 $0$이다. 반면 관리자 $1$을 포함하지 않는 모든 쌍의 두 사람은 처음에는 서로 모르지만, 첫 번째 시간대에 관리자 $1$의 소개를 받을 수 있다. 처음 두 쌍에 대한 시나리오는 독립적으로 고려된다는 점에 유의하라.

예제 케이스 #2에서 관리자 $2$와 비관리자 $5$는 서로 모르며, 두 사람을 모두 아는 사람도 알지 못하므로 이들이 소개되는 데 걸리는 최소 시간은 적어도 $2$분이다. 정확히 2분 후에 두 사람이 소개되게 하는 한 가지 방법은 첫 번째 시간대에 관리자 $3$가 관리자 $1$와 비관리자 $5$를 소개하고, 그 후 두 번째 시간대에 관리자 $1$가 관리자 $2$와 비관리자 $5$를 소개하는 것이다. 두 번째 쌍의 경우, 같은 방식으로 시작하여 2분 안에 관리자 $2$와 비관리자 $5$를 소개한 다음, 세 번째 시간대에 관리자 $2$가 비관리자 $4$와 $5$를 소개할 수 있다. 따라서 $3$분은 $4$와 $5$의 쌍을 소개하는 데 걸리는 시간의 상한이다. 이보다 빠르게 하는 것은 불가능하다.

예제 케이스 #3에서는 새 팀의 두 사람 중 어느 쪽도 상대를 알지 못하므로 어떤 소개도 가능하지 않다.

추가 예제 - 테스트 세트 2

이 추가 예제 케이스에서는 첫 번째 시간대에 관리자 $2$가 관리자 $1$와 $3$를 소개하는 동시에, 관리자 $5$가 관리자 $4$와 비관리자 $6$를 소개할 수 있다. 그다음 두 번째 시간대에 관리자 $3$가 관리자 $1$와 $4$를 소개할 수 있고, 마지막으로 세 번째 시간대에 관리자 $4$가 관리자 $1$와 비관리자 $6$를 소개할 수 있다.