問題文
N頂点の単純無向グラフGが与えられます。頂点には1からNまでの番号が付いており、
i(1≤i≤M)本目の辺は頂点ui と頂点 viを結んでいます。
Q個のクエリが与えられます。
i(1≤i≤Q)番目のクエリでは、aiとbiが与えられ、
Gの頂点aiと頂点biの間にある辺を取り除きます。
クエリの操作を行う前のGと
i(1≤i≤Q)番目までのクエリを処理した後のGについて、全ての連結成分の大きさの積を109+7で割った余りを求めて下さい。
ただし、連結成分の大きさとは、連結な頂点集合における頂点数です。
制約
1≤N≤105
1≤M≤105
1≤Q≤M
1≤ui,vi≤N
1≤ai,bi≤N
ui=vi
i番目のクエリの処理を行う直前の時点で、頂点aiと頂点biの間には辺が存在する。
入力
N M Q
u1 v1
...
uM vM
a1 b1
...
aQ bQ
出力
ans0ans1⋯ansQ
ans0はクエリの処理を行う前のGの全ての連結成分の大きさの積を109+7で割った余り、
ansi(1≤i≤Q)はi番目までのクエリを処理した後の
Gの全ての連結成分の大きさの積を109+7で割った余りです。
サンプル
入力1
5 4 4
1 2
2 3
3 4
4 5
2 3
3 4
4 5
1 2