$\text{[Problem?Discription]}$

給定一個 $n\times m$ 的表格 $a_{i,j}$，你可以恰好進行一次如下操作：

1. 選擇一個格點 $(r,c)$。
2. 對于所有滿足 $i=r$ 或者 $j=c$ 的格點 $(i,j)$，使 $a_{i,j}\leftarrow a_{i,j}?1$。

求操作后所有格點最大值最小可能為多少。

多組數據，滿足 $1\le n\times m\le 1\times 10^5$，且所有數據的 $n\times m$ 的總和不超過 $2\times 10^5$。

$\text{[Analysis]}$

記原來矩陣的最大值為 $t$，顯然由于只能進行一次操作，且一次操作最多讓一個格點的值減小 $1$，所以最終答案要么是 $t$，要么是 $(t?1)$。

思考哪些情況會讓答案為 $(t?1)$。

顯然，當所有取得最大值的格點要么分布在第 $r$ 行要么分布在第 $c$ 列時，我們可以通過一次操作 $(r,c)$ 把所有最大值都干掉；否則答案為 $t$ 不變。

統計每一行每一列有多少個最大值，分別記為 ${\text{cntr}}_i,{\text{cntc}}_j$，顯然第 $i$ 行和第 $j$ 列的最大值的個數即為：

f(i,j)=cntri+cntcj?[ai,j=max?1≤i≤n,1≤j≤m{ai,j}]f(i,j)=\text{cntr}_{i}+\text{cntc}_{j}- \left [a_{i,j}=\max\limits_{1 \leq i \leq n, 1 \leq j \leq m} \{a_{i,j} \}\right ]f(i,j)=cntri?+cntcj??[ai,j?=1≤i≤n,1≤j≤mmax?{ai,j?}]

顯然預先統計出最大值的個數 $\text{cnt}$，如果某個格點 $(i,j)$ 滿足 $f(i,j)=\text{cnt}$，那么這個 $(i,j)$ 就是我們需要的格點。

$\text{Code}$

const int N=1e5+100;int OneZDoubleY(){int n=read(),m=read();vector<int> a[n+2];for(int i=1;i<=n;i++){a[i].push_back(0);for(int j=1;j<=m;j++)a[i].push_back(read());}int maxn=a[1][1];for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)ckmax(maxn,a[i][j]);int cnt=0;vector<int> cntr(n+1),cntc(m+1);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if (a[i][j]==maxn){++cntr[i];++cntc[j];++cnt;}bool flag=false;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){int t=cntr[i]+cntc[j];if (a[i][j]==maxn) t--;if (t==cnt){flag=true;break;}}return printf("%d\n",flag?maxn-1:maxn);
}
//大家可以挑戰一下不用 vector，用 malloc 來處理int main(){int T=read();while (T--) OneZDoubleY();return 0;
}