AC40，WA11

#include <bits/stdc++.h>
using namespace std;
#define int long long
int dis[1000005];
bool is[1000005];
vector < int > a[1000005];
inline void dijkstra(int b){
	memset(dis , 0x3f , sizeof(dis));
	memset(is , 0 , sizeof(is));
	dis[b] = 0;
	priority_queue < pair <int , int> , vector < pair <int , int> > , greater < pair <int , int> > > q; 
	q.push(make_pair(0 , b));
	while(q.size()){
		int y = q.top().first , x = q.top().second;
		q.pop();
		if(is[x]) continue;
		is[x] = 1;
		for(int j = 0;j < a[x].size();j++){
			if(dis[a[x][j]] < dis[x] + 1){
				dis[a[x][j]] = dis[x] + 1;
				q.push(make_pair(dis[a[x][j]] , a[x][j]));
			}
		}
	}
}
inline void bfs(int b){
	memset(dis , 0x3f , sizeof(dis));
	queue <int> q;
	q.push(b);
	dis[b] = 0;
	while(q.size()){
		int f = q.front();
		q.pop();
		for(int i = 0;i < a[f].size();i++){
			int v = a[f][i];
			if(dis[v] > dis[f] + 1){
				dis[v] = dis[f] + 1;
				q.push(v);
			}
		}
	}
}
signed main(){
	int n1 , n2 , m , x , y;
	cin >> n1 >> n2 >> m;
	int n = n1 + n2;
	for(int i = 1;i <= m;i++){
		cin >> x >> y;
		a[x].push_back(y);
		a[y].push_back(x);
	}
	bfs(1);
	int maxn = 0 , id = 0;
	for(int i = 1;i <= n;i++){
		if(maxn < dis[i] && dis[i] != 0x3f3f3f3f3f3f3f3f){
			maxn = dis[i];
			id = i;
		}
	}
	bfs(n);
	maxn = 0;
	int idd = 0;
	for(int i = 1;i < n;i++){
		if(maxn < dis[i] && dis[i] != 0x3f3f3f3f3f3f3f3f){
			maxn = dis[i];
			idd = i;
		}
	}
	a[id].push_back(idd);
	a[idd].push_back(id);
	bfs(1);
	cout << dis[n];
    return 0;
}