注意

この問題の実行時間制限は 5.000 秒です。

問題文

$K$ 個の連結単純無向グラフ $G_1, G_2, \cdots, G_K$ が与えられます。各グラフ $G_i$ は頂点が $N_i$ 個、辺が $M_i$ 本あり、頂点はそれぞれ $V_{i,1}, V_{i,2}, \cdots, V_{i,N_i}$ と番号が振られています。グラフ $G_i$ の $j$ 番目の辺は頂点 $V_{i, A_{i,j}}$ と $V_{i, B_{i,j}}$ を結びます。

連結無向グラフ $G$ を次のように作ります。

１．$G$ の頂点は $V_X, V_Y, V_{i, j} \ (1\le i\le K, 1\le j \le N_i)$ の $(2 + \sum_{i=1}^K N_i)$ 個である。

２．すべての $1 \le i \le K$ に対し、グラフ $G_i$ に含まれる辺 $M_i$ 本をグラフ $G$ にすべて張る。

３．すべての $1 \le i \le K$ に対して、 $V_X$ と $V_{i,1}$ との間、 $V_Y$ と $V_{i,2}$ との間に辺を張る。

グラフ $G$ の全域木の個数を $998244353$ で割った余りを求めてください。

制約

• 入力はすべて整数
• $2 \le K \le 210$
• グラフ $G_i$ は連結である。
• グラフ $G_i$ は単純である。すなわち、自己ループや多重辺を含まない。
• $2 \le N_i \le 60$
• $1 \le M_i \le \frac{N_i(N_i-1)}{2}$
• $1 \le A_{i,j} \lt B_{i,j} \le N_i$

入力

$K$
$\text{graph}_1$
$\text{graph}_2$
$\vdots$
$\text{graph}_K$

ただし、 $\text{graph}_i$ はグラフ $G_i$ の入力を表し、次のように与えられる。

$N_i$ $M_i$
$A_{i,1}$ $B_{i,1}$
$A_{i,2}$ $B_{i,2}$
$\vdots$
$A_{i,{M_i}}$ $B_{i,{M_i}}$

出力

答えを出力せよ。

サンプル

サンプル1

入力サンプルをコピー

入力

2
2 1
1 2
3 3
1 2
2 3
1 3

出力

17

入力は以下のように読みます。

• 1行目：2は $K$ の値を表す。
• 2行目：2 1はグラフ $G_1$ の頂点数が $2$、辺数が $1$ であることを表す。
• 3行目：1 2はグラフ $G_1$ において頂点 $V_{1,1}$ と $V_{1,2}$ との間に辺があることを表す。
• 4行目：3 3はグラフ $G_2$ の頂点数が $3$、辺数が $3$ であることを表す。
• 5行目：1 2はグラフ $G_2$ において頂点 $V_{2,1}$ と $V_{2,2}$ との間に辺があることを表す。
• 6行目：2 3はグラフ $G_2$ において頂点 $V_{2,2}$ と $V_{2,3}$ との間に辺があることを表す。
• 7行目：1 3はグラフ $G_2$ において頂点 $V_{2,1}$ と $V_{2,3}$ との間に辺があることを表す。

グラフ $G$ は以下のようになります。

このグラフの全域木の個数は全部で $17$ 個あるので、 $17$ を出力します。

4
7 13
1 5
2 7
3 4
5 6
1 2
3 7
2 5
1 3
3 5
4 5
5 7
2 3
1 4
7 17
2 5
2 3
2 7
1 2
3 6
3 4
5 6
3 7
1 3
2 6
2 4
1 5
3 5
1 4
6 7
1 6
5 7
4 3
3 4
2 4
1 3
5 8
1 3
2 3
2 4
1 5
3 5
3 4
1 4
4 5

469335995