{"problem":{"name":"A. Hey Gamers","description":{"content":"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 gam","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10268A"},"statements":[{"statement_type":"Markdown","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## Input\n\nThe 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. \n\n## Output\n\nFor 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. \n\n[samples]\n\n## Scoring\n\n*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.\n\n## Note\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. 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.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**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.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10268A","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}