くろうさが選ぶ頂点 \(u\) を決めたときに答えを求める方法をまず考えます． \(u\) から BFS を行い，他の頂点への最短距離を求めます． これらの距離の最大値を \(D\) と置きます． まず，答の下界として，次の値が得られます．

• \(\max_{0 \leq i \leq D} (i+ceil((\)距離が\(i+1\)以上の頂点の個数\()/2))\)

この値が実は答えになっています． これは次のようにわかります． 操作を逆順に見て，頂点を \(1\) 個か \(2\) 個消していく問題だと考えます． ここで，できるだけ距離の長い頂点を選んで消すことを考えます． 具体的には，まず距離最大の頂点を\(1\) つ消すことにして，さらに同時に消せる頂点が（あるなら）その中で距離最大のものを消します．

\(1\) 回の操作で上の値が \(1\) 減ることを示します． 消した頂点が \(1\) つの場合，グラフはパスになっているので，上の値が \(1\) 減るのは明らかです．

消した頂点が \(2\) つの場合，それらの \(u\) からの距離を \(D,x\) とおくと，\(i <x\) に関しては，\(\max\) の中の値が \(1\) 減っています． \(x \leq i < D\) について考えると，距離 \(i+1\) の頂点が \(1\) つしか無い（さもなくば距離 \(i+1\) の頂点を消すことができたはず）ことから，\(\max\) の中の値は操作前の段階で \(D\) 以下で，操作後に \(D-1\) 以下だとわかります． また，\(i=D\) では操作前の \(\max\) の中身は \(D\) です． 以上より，\(1\) 回の操作で上の \(\max\) の値は \(1\) 減ります．

元の問題に戻ると，\(u\) を動かして上の値が取る最大値を求めればよいです． \(\max\) の \(\max\) なので，\(u,i\) を動かして \(\max\) を取る，と考えられます．

最適値を与える \(u,i\) を取ったとします． このとき，\(u\) から距離 \(i\) にある頂点はちょうど \(1\) 個だと思ってよいです． そうでない場合，\(i\) の代わりに \(i-1\) を使うことで損しない解が得られます． \(u\) から距離 \(i\) にある頂点を \(a\) と呼ぶことにします．

答えの自明な下界として，\(ceil((N-1)/2))\) があります． 以降は，答えがこれより真に大きくなるケースのみ考えることにします． すると，\(a\) が \(G\) の関節点であると思ってよくなります． \(a\) が \(G\) の関節点でないケースは，\(i=0\), \(i=D\) の \(2\) つのパターンが考えられます． \(i=0\) のときは答えが \(ceil((N-1)/2))\) になるので無視できます．

\(i=D\) のときを考えます．”\(u\) からの距離 \(j\) の頂点がちょうど \(1\) つ” を満たす \(j\) (\(j<D\)) のうち最大のものを取ってみます． 各 \(k\) (\(j<k<D\)) について，\(u\) からの距離 \(k\) の頂点が \(2\) 個以上存在することから，距離 \(j+1\) 以上の頂点の個数は \(2 \times (D-j)-1\) 個以上あるとわかります． すると，\(i\) の代わりに \(j\) を使っても \(\max\) の値が \(D\) になることが確認できます．

以降は，関節点 \(a\) と頂点 \(u\) を動かして，上の値を最大化することを考えます． 関節点 \(a\), 頂点 \(u\) に対して，\(F(a,u)\) を以下のように定義します．

• \(F(a,u)= 2 \times (G\) 上での \(a-u\) 間の最短距離 \()-(a\) を \(G\) から削除したあとの \(u\) の属する連結成分のサイズ\()\)

\(F(a,u)\) の最大値を求めれば，答えは \(ceil((N-1+F(a,u))/2)\) と求まります．

ところで，\(a\) が関節点であっても，\(u\) からの距離が \(a\) と同じ別の頂点が存在することはあります．ですが，その場合でも答えが不正に大きくなるということはありません．

以下では，\(F(a,u)>0\) となる \(a,u\) のみを考えることにします．

最適値を達成する\(a,u\) を探すために，以下の条件を満たす補助頂点 \(v\) を考えます．

• \(G\) から \(a\) を削除したあと，\(u\) と \(v\) が異なる連結成分にある．

このような \(v\) がもしわかっていれば，\(F(a,u)\) の最大値を求めるのは簡単です． まず \(v\) から BFS を行います． その後，各二重連結成分 \(C\) について，その成分内の頂点の中で最も \(v\) に近いものを \(a\) として考えてみます． \(u\) として取るべきは，\(a\) から見て \(C\) 側にある中で最も遠い頂点ですが，これは単に，DFS 木で \(C\) に対応する部分木の中から(\(v\) からのBFSでの )距離最大の頂点を取ればよいです．

これで \(v\) がわかっている場合は問題を解くことができました． 以下，\(v\) として試すべき候補の頂点を見つける方法を説明します．

\(G\) を二重連結成分分解し，頂点と二重連結成分を結んでできる木を \(T\) と置きます． \(v\) の候補としては，\(T\) の直径の端点を試せばよいです． 以下この事実を証明します．

直径の端点を \(p,q\) と置きます． そして，最適解を与える \(a,u\) の組を一つ固定します． このとき，\(T\) 上での \(a-u\) 間距離が最小になるようなものを取ることにします．

このアルゴリズムが正当でないと仮定し矛盾を導きます． \(p,q\) どちらも \(v\) の候補として適切ではない，ということは，\(p,q\) はどちらも \(a\) から見て \(u\) 側の連結成分に所属しています．

まず，\(T\) 上で \(p-q\) パスが \(a-u\) パスと共通部分を持たないときのことを考えます． このとき，以下のようにして \(F(a,u) \leq 0\) であることが確認できます． まず，\(a-u\) パスの長さを \(2d\)，\(p-q\) パスの長さを \(2e\) とおきます． ここで \(d \leq e\) です．

\(a-u\) パス上に存在する二重連結成分だけを考えてできるグラフ \(G'\) を考えます．この \(G'\) に対応する \(F'(a,u)\) を考えると，まず，\(F'(a,u) \leq d\) です．これは次のようにわかります．\(u\) から BFS をしたとき，距離が \(i\) になる頂点が \(1\) 個しかない，というような \(i\) (\(i>0\))の個数が \(F'(a,u)\) の上界です．そしてこのような \(i\) の個数は \(d\) で抑えられています．よって，\(F'(a,u) \leq d\) です．

\(p-q\) パス上にあって，\(G'\) に含まれないような頂点は少なくとも \(e\) 個存在します． よって，\(F(a,u) \leq F'(a,u)-e \leq 0\) が従います． そのためこのようなケースは考える必要がないとわかります．

\(p-q\) パスと \(a-u\) パスが共通部分を持つときのことを考えます．

この共通部分も何らかのパスです．このパスの端点のうち，\(a\) に近いものを \(w\) とおきます． また，一般性を失わず，\(p-q\) パス上において，\(p\) に近い頂点が \(w\) であるとします．

\(w\) が \(G\) の頂点に対応する場合を考えます． この場合は，\(a-w\) 間距離と \(p-w\) 間距離の不等式評価から，\(a\) の代わりに \(w\) を選べばよいことがわかります． やることは \(p-q\) と \(a-u\) が共通部分を持たない場合とほぼ同様なので省略します．

\(w\) が \(G\) の二重連結成分に対応する場合を考えます． この場合も今まで処理したケースと同様ですが，最も不等式評価に気をつかう必要があります． まず，\(w\) から \(u\) 側に \(1\) 回進んだ先の頂点を \(z\) とおきます． \(a\) の代わりに \(z\) を用いれば良いことを示します． \(a-z\) パスの長さを \(2d\)，\(p-z\) パスの長さを \(2e\) とおきます． まず，\(d \leq e-1\) です． \(a\) は \(G\) の関節点であり，\(T\) 上では葉になっていないことを考えて，右辺に \(-1\) を足しています． 次に，\(p-z\) パス上にある頂点であって，\(a-z\) パス上の二重連結成分に含まれないものは少なくとも \(e-1\) 個存在します． よって，\(F(z,u) \geq F(a,u)-d+(e-1) \geq F(a,u)\) となります． 等号が成立する可能性もありますが，その場合は \(a−u\) 間距離が最小という最初の条件に矛盾することになります． よって，このようなケースも考える必要がありません．

以上より，\(T\) 上の直径の端点を \(v\) として試せばよいことが示されました．

すべての操作は \(O(N+M)\) 時間で行えます．

解答例