这道题非常简单啊！

我们考虑以下一条最短路的构成，一定是 $1$ 所在的连通块的一条 $1$ 到 $x$ 的路径，一条 $x$ 到 $y$ 的边（即我们添加的那条边），一条 $n_1+n_2$ 所在的连通块的 $y$ 到 $n_1+n_2$ 的路径。

显然三个区域并不关联，我们贪心地让三个最大。

也就是说吗，我们找一条 $1$ 所在的连通块的最长路，再找一条 $n_1+n_2$ 所在的连通块的最长路，答案即为两者之和加一。

由于需要跑 BFS 最短路，时间复杂度为 $O(n+m)$。

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const LL N=2e6+5;
LL n1,n2,m,x,y,dis[N],mn,mn2;
vector<LL>v[N];
queue<LL>q;
void bfs(LL x)
{while(!q.empty())q.pop();q.push(x);while(!q.empty()){LL t=q.front();q.pop();for(LL i:v[t]){if(dis[i]>dis[t]+1){dis[i]=dis[t]+1;q.push(i);}}}
}
int main()
{scanf("%lld%lld%lld",&n1,&n2,&m);for(int i=1;i<=m;i++){scanf("%lld%lld",&x,&y);v[x].push_back(y);v[y].push_back(x);}memset(dis,127,sizeof(dis));dis[1]=0,dis[n1+n2]=0;bfs(1),bfs(n1+n2);for(int i=2;i<=n1;i++)mn=max(mn,dis[i]);for(int i=n1+1;i<n1+n2;i++)mn2=max(mn2,dis[i]);printf("%lld",mn+mn2+1);
}