AGC039 B - Graph Partition (500)

二部グラフらしい

ある点からある点へ偶数でも奇数でも到達できる場合、明らかに分割不可能

二点間の最小距離の最大値+1が答えになりそう

この経路上で1ずつグループを増加させれば良い

偶奇に問題が無いのは確認できているので構築できる

グラフの直径と呼ぶらしい

上の実際の手順としては、

DFSで偶奇の確認

ワーシャルフロイド法で最短距離を求める

最短距離一覧から最大値を求める