After applying the operation on \((u,v)\), the shortest path from vertex \(1\) to vertex \((N_1+N_2)\) is composed of:

• a shortest path from vertex \(1\) to vertex \(u\);
• the (added) edge connecting vertices \(u\) and \(v\);
• a shortest path from vertex \(v\) to vertex \((N_1+N_2)\).

Thus, the maximum value of \(d\) is the sum of the maximum shortest distance from vertex \(1\) to a vertex \(u\), and the maximum shortest distance from a vertex \(v\) to vertex \((N_1+N_2)\), plus \(1\). The latter coincides with the maximum shortest distance from vertex \((N_1+N_2)\) to a vertex \(v\), so it is sufficient to find the shortest distance from vertices \(1\) and \((N_1+N_2)\) to each vertex (that are connected).

One can find the shortest distance from a vertex \(s\) to each vertex with Breadth-First Search (BFS). We will explain it briefly (for more details, please refer to the online resources).

1. Prepare an array \(\mathrm{dist}\) of length \((N_1+N_2)\) to store the shortest distance from vertex \(s\), with each element initialized with \(-1\), and an empty queue.
2. Let \(\mathrm{dist}_s=0\), and push \(s\) to the queue.
3. While the queue is non-empty, do the following:
   • Let \(x\) be the top element of the queue. Remove \(x\) from the queue.
   • For each vertex \(y\) adjacent to \(x\), if \(\mathrm{dist}_y = -1\), then let \(\mathrm{dist}_y = \mathrm{dist}_x + 1\), and push \(y\) to the queue.

After completing the procedure, \(\mathrm{dist}_x\) stores the shortest distance from vertex \(s\) to vertex \(x\) (or \(-1\) if \(s\) and \(x\) are disconnected).
You can find the correct answer by performing it for \(s=1,N_1+N_2\) to find the maximum distances.

Sample code (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;
}