P9413 "NnOI R1-T2" Wind Isle

"Named after the wind, the isles sing together." — Wind Isle.

Wind Isle is an archipelago with $n$ rows and $m$ columns. The cell in row $i$ and column $j$ is denoted as $(i,j)$. The gravity system of Wind Isle is very strange. The gravity coefficient of $(i,j)$ is $g_{i,j}=a_i+b_j$. Here, $a$ and $b$ are two known arrays of lengths $n$ and $m$. We say islands $(x,y)$ and $(z,w)$ are **adjacent** if and only if $|x-z|+|y-w|=1$. We say $(x,y)$ and $(z,w)$ are **connected** if and only if at least one of the following holds: * $(x,y)$ and $(z,w)$ are adjacent, and $g_{x,y}=g_{z,w}$. * There exists another island $(u,v)$ such that $(x,y)$ is connected to $(u,v)$ and $(u,v)$ is connected to $(z,w)$. That is, the connected relation **is transitive**. We define an unordered set of distinct islands $\{(x_i,y_i)\}$ to be a **same-color connected component** if and only if every pair of islands in the set is connected. Find the largest same-color connected component, and output its size and the number of such components.

**This problem has multiple test cases**. The first line contains a positive integer $T$, representing the number of testdata groups in this test. For each test case: The first line contains $n$ and $m$, representing the number of rows and columns of Wind Isle. The next line contains $n$ integers, representing array $a$. The next line contains $m$ integers, representing array $b$.

Output $T$ lines. Each line contains the answer for that test case (the maximum component size and the count).

### Sample Explanation For sample $1$: For the first test case, the gravity coefficients are as follows: ``` 2 3 4 5 3 4 5 6 3 4 5 6 ``` ``` 2 3 4 5 * # ? . * # ? . ``` The cells marked by symbols form the largest same-color connected components. The size is $2$, and there are $4$ such components. ### Constraints For $20\%$ of the data, $n,m \le 10^3$. For another $20\%$ of the data, all $b_i$ are equal. For another $20\%$ of the data, the answer to the second question is guaranteed to be $1$. For another $20\%$ of the data, $T=1$. The test points represented by these four subtasks do not include each other. For $100\%$ of the data, $1 \le T \le 5$, $1 \le n,m \le 10^5$, $1 \le a_i,b_i \le 10^9$. ### Source | Item | People | |:-:|:-:| | idea | Kevin0501 | | std | Kevin0501 | | data | EstasTonne | | check | EstasTonne | | solution | Kevin0501 | Translated by ChatGPT 5