Page not loading? Try clicking here.
Placeholder

#10388

Introductions Organization 20s 1024MB

Problems

After Apricot Rules LLC went through a reorganization, a new large team was formed containing \mathbf{M} managers and \mathbf{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 1 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.


Input

The first line of the input gives the number of test cases, \mathbf{T}. \mathbf{T} test cases follow. Each test case begins with a line containing three integers \mathbf{M}, \mathbf{N}, and \mathbf{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 \mathbf{M} and non-managers are numbered from \mathbf{M} + 1 through \mathbf{M} + \mathbf{N}. Then, \mathbf{M} + \mathbf{N} lines follow with \mathbf{M} + \mathbf{N} characters each. The j-th character on the i-th of these lines \mathbf{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 \mathbf{P} more lines; the k-th of which contains a pair of integers \mathbf{A_k} and \mathbf{B_k} each, representing the team member numbers of the k-th pair we are interested in.


Output

For each test case, output one line containing Case #x: y_1\ y_2\ y_3 \cdots y_\mathbf{P}, where x is the test case number (starting from 1) and y_i is -1 if team members \mathbf{A_k} and \mathbf{B_k} cannot get to know each other, or the shortest amount of time (in minutes) since the process starts until they do.


Example #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
Case #1: 1 1 0
Case #2: 2 3
Case #3: -1
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.

Example #2

1
5 1 1
YYNNNN
YYYNNN
NYYYNN
NNYYYN
NNNYYY
NNNNYY
1 6
Case #1: 3

Source

GCJ 2021iow C

You must sign in to write code.