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:
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:
For each test case, output one line containing the answer:
*For all subtasks*
$1 <= t <= 10$
$1 <= r, c <= 500$
There is exactly zero or two of each letter.
There is at least one letter in the grid.
*Subtask 1* (20 points):
$1 <= r, c <= 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 <= r, c <= 50$
*Subtask 4* (25 points):
No additional constraints.
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.
## Input
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.
## Output
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.
[samples]
## Scoring
*For all subtasks*$1 <= t <= 10$$1 <= r, c <= 500$There is exactly zero or two of each letter.There is at least one letter in the grid.*Subtask 1* (20 points):$1 <= r, c <= 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 <= r, c <= 50$*Subtask 4* (25 points):No additional constraints.
## Note
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.
**Definitions**
Let $ \mathbf{v} = (A, B, C, D, E, F, G, H, I, J) \in \mathbb{Z}_{\geq 0}^{10} $ be the initial counts of Tai: Aqua, Breath, Copper, Dahnium, Earth, Fire, Gold, Hydrargyrum, Iron, Jodium.
Let $ \mathcal{K} $ be a multiset of Kshons, each of the form $ (n, x \to y) $, where:
- $ n \in \mathbb{Z}_{>0} $ is the number of copies of the Kshon,
- $ x \in \{A, B, C, D, E, F, G, H, I, J\} $ is the input Tai,
- $ y \in \{A, B, C, D, E, F, G, H, I, J, *\} $ is the output Tai, with $ * $ denoting any Tai (Pkast).
**Constraints**
1. $ 0 \leq A, B, \dots, J \leq 10^{12} $
2. $ 0 \leq K \leq 10^{12} $
3. For each Kshon $ (n, x \to y) \in \mathcal{K} $, $ 1 \leq n \leq 10^{12} $
4. All Kshons in $ \mathcal{K} $ are distinct (i.e., no duplicate $ (x \to y) $ pairs).
**Objective**
For each Tai $ t \in \{A, B, C, D, E, F, G, H, I, J\} $, compute the maximum possible final count of $ t $, assuming:
- Each Kshon can be used at most $ n $ times (where $ n $ is its multiplicity).
- **Ankoray**: $ x \to xx $ (one unit of $ x $ becomes two units of $ x $).
- **Pkast**: $ x \to * $ (one unit of $ x $ becomes one unit of *any* Tai, chosen optimally).
- Kshons are used in sequence; outputs can be reused as inputs.
- The transformation for each Tai is computed independently (i.e., maximize each Tai’s count separately, assuming optimal allocation of Pkast outputs).
**Formal Objective per Tai $ t $:**
Maximize $ f_t $, the final count of Tai $ t $, under the constraints of the available Kshons and initial $ \mathbf{v} $, where:
- Ankoray $ x \to xx $: increases count of $ x $ by 1 per use (net gain).
- Pkast $ x \to * $: allows conversion of $ x $ to any Tai (including $ t $), at 1:1 ratio.
- Use of Kshons is constrained by their multiplicities and the availability of inputs (including those generated during the process).
The problem reduces to: for each target Tai $ t $, compute the maximum number of units of $ t $ that can be generated via a sequence of Ankoray and Pkast operations, starting from $ \mathbf{v} $, with unlimited reuse of generated material.