#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/16/problems/C

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████████████████████████████████████████

Subset Maxima - Repovive Premier Round 6 | Repovive | Repovive

16C. Subset Maxima

1500 pts1s256 MB

You are given $m$ conditions about an unknown sequence $p_1, p_2, \ldots, p_n$ .

The sequence must be a permutation of the integers from $1$ to $n$ .

For each condition $i$ , an integer $c_i$ and a non-empty set $S_i$ of positions are given. The condition is satisfied if

$\max\limits_{v \in S_i} p_v = c_i$ .

For each test case, count the number of permutations $p_1, p_2, \ldots, p_n$ that satisfy all conditions. Since the answer can be large, output it modulo $998244353$ .

Constraints

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
$0 \le m \le 2 \times 10^5$
$1 \le k_i \le n$
$1 \le c_i \le n$
$1 \le s_{i,j} \le n$
For each $i$ , the values $s_{i,1}, s_{i,2}, \ldots, s_{i,k_i}$ are pairwise distinct
The sum of $n$ over all test cases is at most $2 \times 10^5$
The sum of $m$ over all test cases is at most $2 \times 10^5$
The sum of all $k_i$ over all test cases is at most $2 \times 10^5$

Input

t

\left. \begin{array}{l} n \quad m \\ k_1 \quad c_1 \quad s_{1,1} \quad s_{1,2} \quad \cdots \quad s_{1,k_1} \\ k_2 \quad c_2 \quad s_{2,1} \quad s_{2,2} \quad \cdots \quad s_{2,k_2} \\ \vdots \\ k_m \quad c_m \quad s_{m,1} \quad s_{m,2} \quad \cdots \quad s_{m,k_m} \end{array} \right\} \times t

Output

\left. \begin{array}{l} ans \end{array} \right\} \times t

Samples

Input

Case 1

3 0

Case 2

3 1
2 2 1 2

Case 3

4 2
3 3 1 2 3
2 2 2 3

Case 4

4 2
2 3 1 2
2 3 3 4

Case 5

4 1
3 2 1 2 3

Explanation

Case 1

There are no conditions, so every permutation of $1,2,3$ is valid.

Case 2

The first two positions must contain $1$ and $2$ in any order, and the remaining position must contain $3$ .

Case 3

The first condition needs one of positions $1,2,3$ to contain $3$ . The second condition forces positions $2$ and $3$ to contain $1$ and $2$ in some order, so position $1$ must contain $3$ .

Case 4

The value $3$ would have to appear in both subsets $\{1,2\}$ and $\{3,4\}$ , but these subsets are disjoint.

Case 5

The first three positions would all need values at most $2$ , but only two values are at most $2$ .

Output

Case 1

Case 2

Case 3

Case 4

Case 5

You are given $m$ conditions about an unknown sequence $p_1, p_2, \ldots, p_n$ .

The sequence must be a permutation of the integers from $1$ to $n$ .

For each condition $i$ , an integer $c_i$ and a non-empty set $S_i$ of positions are given. The condition is satisfied if

$\max\limits_{v \in S_i} p_v = c_i$ .

For each test case, count the number of permutations $p_1, p_2, \ldots, p_n$ that satisfy all conditions. Since the answer can be large, output it modulo $998244353$ .

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
$0 \le m \le 2 \times 10^5$
$1 \le k_i \le n$
$1 \le c_i \le n$
$1 \le s_{i,j} \le n$
For each $i$ , the values $s_{i,1}, s_{i,2}, \ldots, s_{i,k_i}$ are pairwise distinct
The sum of $n$ over all test cases is at most $2 \times 10^5$
The sum of $m$ over all test cases is at most $2 \times 10^5$
The sum of all $k_i$ over all test cases is at most $2 \times 10^5$

t

\left. \begin{array}{l} n \quad m \\ k_1 \quad c_1 \quad s_{1,1} \quad s_{1,2} \quad \cdots \quad s_{1,k_1} \\ k_2 \quad c_2 \quad s_{2,1} \quad s_{2,2} \quad \cdots \quad s_{2,k_2} \\ \vdots \\ k_m \quad c_m \quad s_{m,1} \quad s_{m,2} \quad \cdots \quad s_{m,k_m} \end{array} \right\} \times t

\left. \begin{array}{l} ans \end{array} \right\} \times t

There are no conditions, so every permutation of $1,2,3$ is valid.

The first two positions must contain $1$ and $2$ in any order, and the remaining position must contain $3$ .

The first condition needs one of positions $1,2,3$ to contain $3$ . The second condition forces positions $2$ and $3$ to contain $1$ and $2$ in some order, so position $1$ must contain $3$ .

The value $3$ would have to appear in both subsets $\{1,2\}$ and $\{3,4\}$ , but these subsets are disjoint.

The first three positions would all need values at most $2$ , but only two values are at most $2$ .

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

16C. Subset Maxima

Constraints

Input

Output

Samples

16C. Subset Maxima

Constraints

Input

Output

Samples