\((u,v)\) に対して操作をした後のグラフにおける頂点 \(1\) から頂点 \(N_1+N_2\) への最短経路は以下のようなものになります。

• 頂点 \(1\) から頂点 \(u\) へ最短経路を通って行く
• 頂点 \(u, v\) を結ぶ辺(追加した辺)を通る
• 頂点 \(v\) から頂点 \(N_1+N_2\) へ最短経路を通って行く

よって、\(d\) の最大値は頂点 \(1\) から頂点 \(u\) への最短距離の最大値と頂点 \(v\) から頂点 \(N_1+N_2\) への最短距離の最大値の和に \(1\) を加えたものになります。特に後者は頂点 \(N_1 +N_2\) から頂点 \(v\) への距離の最大値に一致するため、頂点 \(1,N_1+N_2\) から(その頂点から連結な)各頂点までの最短距離を求められれば良いです。

頂点 \(s\) から各頂点までの最短距離は幅優先探索によって高速に求められます。以下、簡単にその内容を示します(より詳細な説明に関しては検索してください)。

1. 頂点 \(s\) からの最短距離を表す長さ \(N_1+N_2\) の配列 \(\mathrm{dist}\) を用意し、すべて \(-1\) で初期化する。また、空のキューを用意する。
2. \(\mathrm{dist}_s=0\)とし、キューに \(s\) を追加する。
3. キューが空でない間、次の操作をする。
   • キューの先頭を取り出し、\(x\) とする。キューから \(x\) を削除する。
   • \(x\) に隣接する頂点 \(y\) それぞれについて、\(\mathrm{dist}_y = -1\) ならば \(\mathrm{dist}_y = \mathrm{dist}_x + 1\) とし、キューに \(y\) を追加する。

以上が終了した時、\(\mathrm{dist}_x\) が頂点 \(s\) から頂点 \(x\) までの最短距離( \(s,x\) が非連結ならば \(-1\) )です。
上記処理を \(s=1,N_1+N_2\) で行って距離の最大値を求めることで本問に正解出来ます。

実装例(C++)

#include <bits/stdc++.h>
using namespace std;

int get(vector<vector<int>> E,int s){
	int n = E.size();
	vector<int> dist(n,-1);
	
	dist[s] = 0;
	queue<int> Q;
	Q.push(s);
	
	while(Q.size()>0){
		int x = Q.front();
		Q.pop();
		for(int i=0;i<E[x].size();i++){
			int y = E[x][i];
			if(dist[y]==-1){
				dist[y] = dist[x]+1;
				Q.push(y);
			}
		}
	}
	
	return *max_element(dist.begin(),dist.end());
}

int main() {
    
	int N1,N2,M;
	cin>>N1>>N2>>M;
	
	vector<vector<int>> E(N1+N2);
	
	for(int i=0;i<M;i++){
		int a,b;
		cin>>a>>b;
		a--,b--;
		E[a].push_back(b);
		E[b].push_back(a);
	}
	
	cout<<get(E,0)+get(E,N1+N2-1)+1<<endl;
	
	return 0;
}