atcoder ABC309 D - Add One Edgeの勉強

・考え方：bfsで解く。1から行ける頂点の距離をdist1、N1+N2から行ける頂点の距離をdist2とする。あとはそれぞれのmaxを取って+1したのが最大の距離になる。

from collections import deque

#入力
n1,n2,m=map(int, input().split())

n=n1+n2

g=[[]for _ in range(n)]
for _ in range(m):
  a,b=map(int, input().split())
  a-=1
  b-=1
  g[a].append(b)
  g[b].append(a)


#リストの用意  
dist1=[-1 for _ in range(n)]
dist2=[-1 for _ in range(n)]

que=deque()


#bfs
def bfs (que,dist):
  while len(que)!=0:
    v=que.popleft()
  
    for nv in g[v]:
      if dist[nv]!=-1:
        continue
      dist[nv]=dist[v]+1
      que.append(nv)

#main
dist1[0]=0    #頂点1から。(-1しているので0) 
que.append(0)
bfs(que,dist1)

dist2[n-1]=0  #最後の頂点からやる。
que.append(n-1)
bfs(que,dist2)

ma1=max(dist1)
ma2=max(dist2)
print(ma1+ma2+1)