問題文


頂点の単純無向グラフが与えられます。頂点には1からまでの番号が付いており、 本目の辺は頂点 と頂点 を結んでいます。

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

番目のクエリでは、が与えられ、 の頂点と頂点の間にある辺を取り除きます。

クエリの操作を行う前の番目までのクエリを処理した後のについて、全ての連結成分の大きさの積をで割った余りを求めて下さい。

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

制約








番目のクエリの処理を行う直前の時点で、頂点と頂点の間には辺が存在する。

入力




...


...

出力



はクエリの処理を行う前のの全ての連結成分の大きさの積をで割った余り、 番目までのクエリを処理した後の の全ての連結成分の大きさの積をで割った余りです。

サンプル


入力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.14)