Problem Statement

There are towns numbered from $1$ to $N$. Initially, travel between any of the towns is impossible.

You are going to place orders with construction companies to build bridges, each of which connects $2$ distinct towns and makes travel between them possible. You will build $N-1$ bridges so that travel between all towns becomes possible.

The $K$ construction companies are numbered from $1$ to $K$, and company $i$ can be ordered to build $t_i$ kinds of bridges. For $j=1,2,\dots ,t_i$, the bridge with order number $j$ connects town $a_{ij}$ and town $b_{ij}$.

How many ways are there to place $N-1$ orders in total across the companies such that all of the following conditions are satisfied?

• When all the ordered bridges are built, travel between all towns is possible by passing through the bridges
• Orders are placed at least $1$ time with every one of the $K$ construction companies

Find the answer modulo $998244353$.

Constraints

Input

$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}$

Output

Output the number of ways to place the orders, modulo $998244353$.

Sample

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