{"raw_statement":[{"iden":"statement","content":"Download and listen to the problem statement here. It is an MP3 audio file that is 3 minutes and 16 seconds long.\n\nThe game is available for playing!\n\nDownload the following files: \n\nThen, run the game by entering _java -jar Pipes.jar_ in the command line/terminal. Read _README.pdf_ for additional info.\n\nThe first line of input contains $t$, the number of test cases.\n\nThe 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.\n\nEach of the next $r$ lines consist of a string of $c$ characters, representing the grid. Each character is either:\n\nFor each test case, output one line containing the answer:\n\n*For all subtasks*\n\n$1 <= t <= 10$\n\n$1 <= r, c <= 500$\n\nThere is exactly zero or two of each letter.\n\nThere is at least one letter in the grid.\n\n*Subtask 1* (20 points):\n\n$1 <= r, c <= 50$\n\nThe grid contains exactly one pair of equal letters.\n\n*Subtask 2* (25 points):\n\nThe grid contains exactly one pair of equal letters.\n\n*Subtask 3* (30 points):\n\n$1 <= r, c <= 50$\n\n*Subtask 4* (25 points):\n\nNo additional constraints.\n\nThe 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. \n\nThe following illustrates the first test case in the second sample I/O:\n\nThe minimum number of moves is $2$, as illustrated by the following:\n\nThe following images illustrate the rest of the test cases in the second sample I/O:\n\nIt is impossible to connect the letters in both cases, so the output is _F_ for both.\n\n"},{"iden":"input","content":"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. "},{"iden":"output","content":"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. "},{"iden":"scoring","content":"*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."},{"iden":"examples","content":"Input2\n3 6\n-|-|-|\n|g|-g-\n-|-|-|\n2 2\nI|\n|I\nOutput1\nF\nInput3\n4 5\nA|-A|\n-|B|a\n|---a\n||B-|\n3 8\n|--|---|\n-A||B|AB\n|||----|\n3 4\n|--|\nBCCB\n||--\nOutput2\nF\nF\nInput4\n3 10\nA--------A\nx--X--x--X\nE--------E\n2 3\nlol\n|o|\n1 4\nAbbA\n5 8\n-||-bW-W\na||a--||\nZ|Zxbw|w\nz-zx-|-|\nr|-||-|r\nOutputF\nF\nF\n9\n"},{"iden":"note","content":"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."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ \\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.  \nLet $ \\mathcal{K} $ be a multiset of Kshons, each of the form $ (n, x \\to y) $, where:  \n- $ n \\in \\mathbb{Z}_{>0} $ is the number of copies of the Kshon,  \n- $ x \\in \\{A, B, C, D, E, F, G, H, I, J\\} $ is the input Tai,  \n- $ y \\in \\{A, B, C, D, E, F, G, H, I, J, *\\} $ is the output Tai, with $ * $ denoting any Tai (Pkast).  \n\n**Constraints**  \n1. $ 0 \\leq A, B, \\dots, J \\leq 10^{12} $  \n2. $ 0 \\leq K \\leq 10^{12} $  \n3. For each Kshon $ (n, x \\to y) \\in \\mathcal{K} $, $ 1 \\leq n \\leq 10^{12} $  \n4. All Kshons in $ \\mathcal{K} $ are distinct (i.e., no duplicate $ (x \\to y) $ pairs).  \n\n**Objective**  \nFor each Tai $ t \\in \\{A, B, C, D, E, F, G, H, I, J\\} $, compute the maximum possible final count of $ t $, assuming:  \n- Each Kshon can be used at most $ n $ times (where $ n $ is its multiplicity).  \n- **Ankoray**: $ x \\to xx $ (one unit of $ x $ becomes two units of $ x $).  \n- **Pkast**: $ x \\to * $ (one unit of $ x $ becomes one unit of *any* Tai, chosen optimally).  \n- Kshons are used in sequence; outputs can be reused as inputs.  \n- The transformation for each Tai is computed independently (i.e., maximize each Tai’s count separately, assuming optimal allocation of Pkast outputs).  \n\n**Formal Objective per Tai $ t $:**  \nMaximize $ f_t $, the final count of Tai $ t $, under the constraints of the available Kshons and initial $ \\mathbf{v} $, where:  \n- Ankoray $ x \\to xx $: increases count of $ x $ by 1 per use (net gain).  \n- Pkast $ x \\to * $: allows conversion of $ x $ to any Tai (including $ t $), at 1:1 ratio.  \n- Use of Kshons is constrained by their multiplicities and the availability of inputs (including those generated during the process).  \n\nThe 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.","simple_statement":"You start with some amounts of 10 elements (A, B, C, D, E, F, G, H, I, J).  \nYou have K transformation rules (Kshons), each of two types:  \n1. **Ankoray**: One element turns into two of the *same* element (e.g., A → AA).  \n2. **Pkast**: One element turns into *any one* element (e.g., E → *).  \n\nEach rule can be used exactly as many times as given (N times).  \nYou want to know: for each of the 10 elements, what’s the *maximum* amount you can end up with?  \n\nEach element is computed independently.  \nYou can use rules in any order, as many times as allowed.  \nYou start with initial amounts, and can use rules to convert elements into others.  \n\nOutput 10 numbers: the max possible count for each element A through J.","has_page_source":false}