問題文

$1$ から $N$ の番号がついた街があります。はじめはどの街も行き来ができません。

あなたは建設会社に発注して $2$ つの異なる街を繋ぎ行き来可能にする橋を $N-1$ 個を建設し、全ての町が行き来可能になるようにしようとしています。

$K$ 個の建設会社にはそれぞれ $1$ から $K$ までの番号がついており、$i$ 番の建設会社には $t_i$ 種類の橋の建設を発注することができます。 $j=1,2,\dots ,t_i$ について、その橋は街 $a_{ij}$ と 街$b_{ij}$ を繋ぐ、注文番号 $j$ の橋です。

各社合わせて $N-1$ 個の発注をする方法であって、次の条件を すべて 満たすものは何通りありますか。

• 発注した橋をすべて建設したとき、橋を通ることですべての街が行き来可能になる
• $K$ 個すべての建設会社に $1$ 回以上発注している

答えを $998244353$ で割ったあまりを求めてください。

制約

入力

$N$ $K$
$t_1$
$a_{11}$ $b_{11}$
$\vdots$
$a_{1t_1}$ $b_{1t_1}$
$\vdots$
$t_K$
$a_{K1}$ $b_{K1}$
$\vdots$
$a_{Kt_K}$ $b_{Kt_K}$

出力

発注の仕方の数を $998244353$ で割った余りを出力してください。

サンプル

2 1
1
1 2

1

2 1
4
1 2
1 2
1 2
1 2

4

3 2
1
1 2
1
1 2

0

5 3
3
1 2
2 4
3 5
2
3 4
4 5
6
1 2
2 3
3 4
4 5
1 3
1 5

56