Note

The time limit for this problem is 5.000 seconds.

Problem Statement

You are given $K$ connected simple undirected graphs $G_1, G_2, \cdots, G_K$. Each graph $G_i$ has $N_i$ vertices and $M_i$ edges, and its vertices are numbered $V_{i,1}, V_{i,2}, \cdots, V_{i,N_i}$. The $j$-th edge of graph $G_i$ connects vertices $V_{i, A_{i,j}}$ and $V_{i, B_{i,j}}$.

Construct a connected undirected graph $G$ as follows.

1. The vertices of $G$ are the $(2 + \sum_{i=1}^K N_i)$ vertices $V_X, V_Y, V_{i, j} \ (1\le i\le K, 1\le j \le N_i)$.

2. For every $1 \le i \le K$, add all $M_i$ edges of graph $G_i$ to graph $G$.

3. For every $1 \le i \le K$, add an edge between $V_X$ and $V_{i,1}$ and an edge between $V_Y$ and $V_{i,2}$.

Find the number of spanning trees of graph $G$, modulo $998244353$.

Constraints

• All input values are integers.
• $2 \le K \le 210$
• Graph $G_i$ is connected.
• Graph $G_i$ is simple; that is, it contains no self-loops or multiple edges.
• $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$

Input

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

Here, $\text{graph}_i$ denotes the input for graph $G_i$, given in the following format.

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

Output

Output the answer.

Sample

Sample 1

Input

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

Output

17

The input is read as follows.

• Line 1: 2 is the value of $K$.
• Line 2: 2 1 means that graph $G_1$ has $2$ vertices and $1$ edge.
• Line 3: 1 2 means that graph $G_1$ has an edge between vertices $V_{1,1}$ and $V_{1,2}$.
• Line 4: 3 3 means that graph $G_2$ has $3$ vertices and $3$ edges.
• Line 5: 1 2 means that graph $G_2$ has an edge between vertices $V_{2,1}$ and $V_{2,2}$.
• Line 6: 2 3 means that graph $G_2$ has an edge between vertices $V_{2,2}$ and $V_{2,3}$.
• Line 7: 1 3 means that graph $G_2$ has an edge between vertices $V_{2,1}$ and $V_{2,3}$.

Graph $G$ looks as follows.

This graph has $17$ spanning trees in total, so output $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