Subset Maxima - Repovive Premier Round 6 | 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$ .

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

16C. Subset Maxima

Constraints

Input

Output

Samples

16C. Subset Maxima

Constraints

Input

Output

Samples