시간 제한메모리 제한제출정답맞힌 사람정답 비율
40 초 (추가 시간 없음) 1024 MB211100.000%

문제

After Apricot Rules LLC went through a reorganization, a new large team was formed containing $M$ managers and $N$ non-managers. Since many people within the team do not know each other, a number of introduction sessions are to be scheduled. We know exactly which pairs of members already know each other.

The introduction sessions are organized into time slots that take 11 minute. The first time slot starts at 8:00 AM and ends at 8:01 AM. The $i$-th time slot starts $i-1$ minutes after 8:00 AM and ends $i$ minutes after 8:00 AM. During each time slot, there can be one or more introduction sessions. A team member can be assigned to at most one introduction session per time slot. Each introduction session must have exactly three members: an assigned manager $a$ who must be a manager and two others $b$ and $c$ who can be managers or non-managers. The assigned manager $a$ must already know $b$ and $c$ for the session to be scheduled. After the introduction session, $b$ and $c$ are considered to know each other too. If $b$ and/or $c$ are managers, either of them can be the assigned manager of a future introduction session that includes both.

For some pairs of people in the team, we want to know the shortest time that is needed for them to finally know each other, or whether it is impossible for that to happen through the described process. If two people know each other before any introduction sessions happen, we define that shortest time to be $0$ minutes.

Even though we are interested in multiple pairs of people, we are considering the situations independently. That is, the minimum time for each pair can depend on a specific organization of the introduction that is particular to that pair only.

입력

The first line of the input gives the number of test cases, $T$. $T$ test cases follow. Each test case begins with a line containing three integers $M$, $N$, and $P$: the number of managers on the new team, the number of non-managers on the new team, and the number of pairs of team members we are going to ask about, respectively. Managers are numbered from $1$ through $M$ and non-managers are numbered from $M+1$ through $M+N$. Then, $M+N$ lines follow with $M+N$ characters each. The $j$-th character on the $i$-th of these lines $C_{i,j}$ is Y if team members $i$ and $j$ know each other before the introduction process starts, and N otherwise. Then, there are $P$ more lines; the $k$-th of which contains a pair of integers $A_k$ and $B_k$ each, representing the team member numbers of the $k$-th pair we are interested in.

출력

For each test case, output one line containing Case #x: y1 y2 y3 ⋯ yP, where $x$ is the test case number (starting from $1$) and $y_i$ is $-1$ if team members $A_k$ and $B_k$ cannot get to know each other, or the shortest amount of time (in minutes) since the process starts until they do.

제한

  • $1≤T≤100$.
  • $C_{i,j}$ is either uppercase Y or uppercase N, for all $i,j$.
  • $C_{i,j}$ = $C_{j,i}$, for all $i,j$.
  • $C_{i,i}$ = Y, for all $i$. (Team members know themselves.)
  • $1≤A_k
  • $(A_k,B_k)≠(A_ℓ,B_ℓ)$, for all $k≠ℓ$. (No pair of team members is asked about twice.)

Test Set 1 (12점)

  • $1≤M≤3$.
  • $1≤N≤2$.
  • $1≤P≤3$.

Test Set 2 (19점)

  • $1≤M≤50$.
  • $1≤N≤50$.
  • $1≤P≤100$.

예제 입력 1

3
2 2 3
YYYY
YYNN
YNYN
YNNY
2 3
2 4
1 4
3 2 2
YYYNN
YYNYN
YNYNY
NYNYN
NNYNY
2 5
4 5
1 1 1
YN
NY
1 2

예제 출력 1

Case #1: 1 1 0
Case #2: 2 3
Case #3: -1

In Sample Case #1, manager $1$ knows everybody else at the start, and there are no other pairs of people that know each other. Therefore, any pair that includes manager $1$ has $0$ as a result, since they know each other from the start. On the other hand, for any pair that does not include manager $1$, the two people do not know each other from the start, but can be introduced during the first time slot by manager $1$. Notice that the scenarios for the first two pairs considered independently.

In Sample Case #2, manager $2$ and non-manager $5$ do not know each other, nor do they know anyone who knows both of them, so the minimum time for them to be introduced is at least $2$ minutes. One way for them to be introduced after exactly 2 minutes is for manager $3$ to introduce manager $1$ and non-manager $5$ during the first time slot, after which manager $1$ can introduce manager $2$ and non-manager $5$ in the second time slot. For the second pair, we can start the same way to introduce manager $2$ and non-manager $5$ in 2 minutes and then, manager $2$ can introduce non-managers $4$ and $5$ in the third time slot, so $3$ minutes is an upper bound for introducing the pair of $4$ and $5$. It is impossible to do this quicker.

In Sample Case #3, neither person in the new team knows the other, so no introductions are possible.

예제 입력 2

1
5 1 1
YYNNNN
YYYNNN
NYYYNN
NNYYYN
NNNYYY
NNNNYY
1 6

예제 출력 2

Case #1: 3

In this additional Sample Case, manager $2$ can introduce managers $1$ and $3$ in the first time slot, while at the same time manager $5$ can introduce manager $4$ and non-manager $6$. Then, manager $3$ can introduce managers $1$ and $4$ in the second time slot, and finally manager $4$ can introduce manager $1$ and non-manager $6$ in the third time slot.

채점 및 기타 정보

  • 예제는 채점하지 않는다.