AT_abc309_d [ABC309D] Add One Edge

[problemUrl]: https://atcoder.jp/contests/abc309/tasks/abc309_d $ N_1+N_2 $ 頂点 $ M $ 辺の無向グラフがあります。$ i=1,2,\ldots,M $ に対し、$ i $ 番目の辺は頂点 $ a_i $ と頂点 $ b_i $ を結びます。 また、以下を満たすことが保障されます。 - $ 1\ \leq\ u,v\ \leq\ N_1 $ を満たす整数 $ u,v $ に対し、頂点 $ u $ と頂点 $ v $ は連結 - $ N_1+1\ \leq\ u,v\ \leq\ N_1+N_2 $ を満たす整数 $ u,v $ に対し、頂点 $ u $ と頂点 $ v $ は連結 - 頂点 $ 1 $ と頂点 $ N_1+N_2 $ は非連結 次の操作をちょうど $ 1 $ 回行います。 - $ 1\ \leq\ u\ \leq\ N_1 $ を満たす整数 $ u $ と $ N_1+1\ \leq\ v\ \leq\ N_1+N_2 $ を満たす整数 $ v $ を選び、頂点 $ u $ と頂点 $ v $ を結ぶ辺を追加する 操作後のグラフにおいて、頂点 $ 1 $ と頂点 $ N_1+N_2 $ は必ず連結であることが示せます。そこで、頂点 $ 1 $ と頂点 $ N_1+N_2 $ を結ぶ経路の長さ(辺の本数)の最小値を $ d $ とします。 操作で追加する辺を適切に選んだ時にありえる $ d $ の最大値を求めてください。 連結とは？ 無向グラフの頂点 $ u,v $ が連結であるとは、頂点 $ u $ と頂点 $ v $ を結ぶ経路が存在することをいいます。

入力は以下の形式で標準入力から与えられる。 > $ N_1 $ $ N_2 $ $ M $ $ a_1 $ $ b_1 $ $ \vdots $ $ a_M $ $ b_M $

答えを出力せよ。

### 制約 - $ 1\ \leq\ N_1,N_2\ \leq\ 1.5\ \times\ 10^5 $ - $ 0\ \leq\ M\ \leq\ 3\ \times\ 10^5 $ - $ 1\ \leq\ a_i\ \leq\ b_i\ \leq\ N_1+N_2 $ - $ i\ \neq\ j $ ならば $ (a_i,b_i)\ \neq\ (a_j,b_j) $ - $ 1\ \leq\ u,v\ \leq\ N_1 $ を満たす整数 $ u,v $ に対し、頂点 $ u $ と頂点 $ v $ は連結 - $ N_1+1\ \leq\ u,v\ \leq\ N_1+N_2 $ を満たす整数 $ u,v $ に対し、頂点 $ u $ と頂点 $ v $ は連結 - 頂点 $ 1 $ と頂点 $ N_1+N_2 $ は非連結 - 入力はすべて整数 ### Sample Explanation 1 $ u=2,v=5 $ として操作することで $ d=5 $ と出来ます。これが最大値です。 !\[\](https://img.atcoder.jp/abc309/a64d8034b08cfa7d1f655767cc164653.png)