ABC218F Blocked Roads

解説なし

辺の距離が全て1なので、最短距離、最短パスはBFSで求まります。

BFSはなので、すべての辺が通れないときを計算すると、で間に合いません。

元のグラフの最短距離が変化するのは、最短パス上の辺が通れなくなった場合だけです。したがって、このときだけBFSして、最短距離を計算し直せばよいです。

最短パスに属する辺は、同じ頂点を2度通らないことから、高々個なので、となって、間に合います。