Description

For simplicity, assume there are $N$ people and $M$ types of events. Define a binary relation “related” between event types:

• The relation is binary, meaning we only determine whether two types of events are related.
• Events of the same type are always related.
• If event $x$ is related to event $y$, then event $y$ is also related to event $x$.

Let $Q_i = (Q_{i, 1}, Q_{i, 2}, \cdots, Q_{i, C_i})$ be the sequence of events person $i$ plans to complete (called the plan sequence), where $C_i$ is the length of $Q_i$. Each event $Q_{i, j}$ is one of the $M$ event types, and events of the same type may occur multiple times.

As time goes by, each event in every plan sequence will occur exactly once, and no two events occur at the same moment.

To describe the order in which events occur, define $P = (Q_{i_1, j_1}, Q_{i_2, j_2}, \cdots, Q_{i_l, j_l})$ as a development trajectory of the world. $P$ is an ordered sequence satisfying:

1. For every person, each event $Q_{i, j}$ in their plan sequence appears in $P$ exactly once.
2. For any two events $Q_{i, j_1}$ and $Q_{i, j_2}$ belonging to the same plan sequence ($1 \leq j_1 < j_2 \leq C_i$), $Q_{i, j_1}$ must occur before $Q_{i, j_2}$ (i.e., appear earlier in $P$).

Two trajectories $P_1$ and $P_2$ are defined to be essentially different if and only if there exist two related events $Q_{i, j}$ and $Q_{u, v}$ whose relative order differs in $P_1$ and $P_2$. In other words, if in $P_1$ the event $Q_{i, j}$ occurs before $Q_{u, v}$ while in $P_2$ the event $Q_{i, j}$ occurs after $Q_{u, v}$, then $P_1$ and $P_2$ are essentially different; similarly, if in $P_1$ $Q_{i, j}$ occurs after $Q_{u, v}$ but in $P_2$ it occurs before $Q_{u, v}$, then $P_1$ and $P_2$ are also essentially different.

Note: “Essentially the same” is transitive. That is, if $P_1$ is essentially the same as $P_2$, and $P_2$ is essentially the same as $P_3$, then $P_1$ is necessarily essentially the same as $P_3$.

Given $N$, $M$, each person’s plan sequence, and the relatedness between event types, compute how many essentially different world development trajectories there are.

Input Format

• The first line contains an integer denoting the number of people $N$.
• The second line contains an integer denoting the number of event types $M$. All event types are numbered from $0$ to $M - 1$.
• Then, for each person $i$, the description of their plan sequence is given:
  • The first line contains one integer, the sequence length $C_i$.
  • The second line contains $C_i$ integers, giving each event $Q_{i, j}$ in $Q_i$ in order.
• Finally, $M$ lines follow, containing an $M \times M$ matrix dep that describes the relatedness. Each line contains $M$ integers, each being $0$ or $1$. dep(i, j) denotes the integer in the $i$-th row (from top to bottom) and the $j$-th column (from left to right). If dep(i, j) equals $1$, then event type $i$ and event type $j$ are related; otherwise, they are unrelated.

Output Format

Output a single line containing one integer, the number $T$ of essentially different world trajectories.

2 
3 
2 
0 
1 
2 
2 
1 
1 1 0 
1 1 1 
0 1 1

4

Hint

Sample Explanation

There are $2$ people and $3$ event types, with $C_1 = C_2 = 2$. $Q_{1,0} = 0$, $Q_{1,1} = 1$, $Q_{2,0} = 2$, $Q_{2,1} = 1$.

There are $4$ different development trajectories:

• $P_1 = (Q_{1,0}, Q_{1,1}, Q_{2,0}, Q_{2,1})$;
• $P_2 = (Q_{1,0}, Q_{2,0}, Q_{1,1}, Q_{2,1})$;
• $P_3 = (Q_{1,0}, Q_{2,0}, Q_{2,1}, Q_{1,1})$;
• $P_4 = (Q_{2,0}, Q_{2,1}, Q_{1,0}, Q_{1,1})$.

Any other valid development trajectory is necessarily essentially the same as one of these four. For example, $P = (Q_{2,0}, Q_{1,0}, Q_{2,1}, Q_{1,1})$ is essentially the same as $P_3$, because the two trajectories only swap the order of $Q_{1,0} = 0$ and $Q_{2,0} = 2$, and those two event types are unrelated.

Constraints

For $100\%$ of the testdata: $N \leq 10$, $M \leq 15$, $C_i \leq 20$, $T \leq 10^6$.

Translated by ChatGPT 5