Disconnect

まず、クエリを処理し終えた$G$について答えを求めます。(このときの答えが$ans_Q$です。) この$G$から逆順にクエリを処理することを考えると 辺を取り除く操作は、辺を追加する操作になり、Union-Find を用いることができます。 クエリの処理は以下のように行います。

---

頂点$a_i$と頂点$b_i$を、$i=Q$から$i=1$に逆順で結ぶことを考えるとき

(1)頂点$a_i$と頂点$b_i$が既に連結であるとき

$ans_{i-1}$←$ans_{i}$
頂点$a_i$と頂点$b_i$を結ぶ。

(2)頂点$a_i$と頂点$b_i$が、連結ではないとき

頂点$a_i$の属する連結成分の大きさを$a$、頂点$b_i$の属する連結成分の大きさを$b$としたとき、
$ans_{i-1}$←$ans_{i}\times (a+b) / (a\times b)$
頂点$a_i$と頂点$b_i$を結ぶ。

---

実際に答えを求めるときは、割る操作は$mod\ 10^9+7$における逆元をかける操作になることに注意して下さい。