407014: GYM102687 A Hey Gamers

Download and listen to the problem statement here. It is an MP3 audio file that is 3 minutes and 16 seconds long.

The game is available for playing!

Download the following files:

• Pipes.jar
• README.pdf

Then, run the game by entering java -jar Pipes.jar in the command line/terminal. Read README.pdf for additional info.

The first line of input contains $$$t$$$, the number of test cases.

The first line of each test case contains two space-separated integers $$$r$$$ and $$$c$$$, the number of rows and the number of columns in the grid.

Each of the next $$$r$$$ lines consist of a string of $$$c$$$ characters, representing the grid. Each character is either:

• a lowercase or uppercase letter,
• '|' which represents a vertical pipe, or
• '-' which represents a horizontal pipe.

For each test case, output one line containing the answer:

• If it is not possible to connect the pairs of letters through a sequence of clicks, output F.
• If it is possible, output the minimum number of clicks needed to connect all pairs of letters.

For all subtasks

$$$1 \le t \le 10$$$

$$$1 \le r, c \le 500$$$

There is exactly zero or two of each letter.

There is at least one letter in the grid.

Subtask 1 (20 points):

$$$1 \le r, c \le 50$$$

The grid contains exactly one pair of equal letters.

Subtask 2 (25 points):

The grid contains exactly one pair of equal letters.

Subtask 3 (30 points):

$$$1 \le r, c \le 50$$$

Subtask 4 (25 points):

No additional constraints.

2
3 6
-|-|-|
|g|-g-
-|-|-|
2 2
I|
|I

1
F

3
4 5
A|-A|
-|B|a
|---a
||B-|
3 8
|--|---|
-A||B|AB
|||----|
3 4
|--|
BCCB
||--

2
F
F

4
3 10
A--------A
x--X--x--X
E--------E
2 3
lol
|o|
1 4
AbbA
5 8
-||-bW-W
a||a--||
Z|Zxbw|w
z-zx-|-|
r|-||-|r

F
F
F
9

The first sample I/O is valid for all subtasks, while the second and third sample I/O are only valid for the third and fourth subtasks.

The following illustrates the first test case in the second sample I/O:

The minimum number of moves is $$$2$$$, as illustrated by the following:

The following images illustrate the rest of the test cases in the second sample I/O:

It is impossible to connect the letters in both cases, so the output is F for both.