問題文

NN頂点の単純無向グラフGGが与えられます。頂点には1からNNまでの番号が付いており、 i(1iM)i(1\leq i \leq M)本目の辺は頂点uiu_i と頂点 viv_iを結んでいます。

QQ個のクエリが与えられます。

i(1iQ)i(1\leq i \leq Q)番目のクエリでは、aia_ibib_iが与えられ、 GGの頂点aia_iと頂点bib_iの間にある辺を取り除きます。

クエリの操作を行う前のGGi(1iQ)i(1\leq i \leq Q)番目までのクエリを処理した後のGGについて、全ての連結成分の大きさの積を109+710^9+7で割った余りを求めて下さい。

ただし、連結成分の大きさとは、連結な頂点集合における頂点数です。

制約

1N1051\leq N \leq 10^5
1M1051\leq M \leq 10^5
1QM1\leq Q \leq M
1ui,viN1\leq u_i , v_i\leq N
1ai,biN1\leq a_i , b_i\leq N
uiviu_i \neq v_i
ii番目のクエリの処理を行う直前の時点で、頂点aia_iと頂点bib_iの間には辺が存在する。

入力

N M QN \ M \ Q
u1 v1u_1 \ v_1
...
uM vMu_M \ v_M
a1 b1a_1 \ b_1
...
aQ bQa_Q \ b_Q

出力

ans0ans1ansQans_0\\ ans_1\\ \cdots\\ ans_Q


ans0ans_0はクエリの処理を行う前のGGの全ての連結成分の大きさの積を109+710^9+7で割った余り、 ansi(1iQ)ans_i(1\leq i\leq Q)ii番目までのクエリを処理した後の GGの全ての連結成分の大きさの積を109+710^9+7で割った余りです。

サンプル

入力1
5 4 4
1 2
2 3
3 4
4 5
2 3
3 4
4 5
1 2
出力1
5
6
4
2
1

提出


Go (1.21)