問題

https://onlinejudge.u-aizu.ac.jp/problems/2891

$N$ 頂点と $N$ 辺からなる連結無向グラフ $G$ が与えられる。また以下のクエリが $Q$ 回与えられる。クエリのそれぞれに回答せよ。

グラフ $G$ の $2$ 頂点 $a_i, b_i$ を非連結にするために削除する必要がある辺の最小本数を求めよ

制約

$3 \le N \le 10^5$
$1 \le Q \le 10^5$

考え方

連結無向グラフ $G$ は $N$ 頂点と $N$ 辺からなるので、明らかに閉路を $1$ つもつ。またクエリの回答は、 $a_i, b_i$ のどちらも閉路上のパスに存在すれば、 $2$ 本削除する必要があり、そうでない場合は $1$ 本削除すればよいことがわかる。よって求めるべき内容は閉路のパスに含まれる頂点の集合である。

ここで、閉路に含まれない頂点を取り除いても、閉路のパスには影響がないので取り除くことにしよう。頂点の次数が $1$ の頂点 $v_i$ から順に辺を削除してくことで $v_i$ と隣接する頂点の次数が $1$ 減ることになる。そうして貪欲に各頂点の次数を下げていったときに最終的にすべての頂点の次数が $0$ になれば $G$ は閉路を持たない(ただし今回はありあえない)。そうでない場合は残っている次数 $2$ 以上の頂点の集合が閉路のパスになる。