Organizing a Music Festival
Contest: Codeforces Global Round 15
Difficulty rating: 3400
Tags: dfs and similar, math

You are the organizer of the famous "Zurich Music Festival". There will be $$$n$$$ singers who will perform at the festival, identified by the integers $$$1$$$, $$$2$$$, $$$\dots$$$, $$$n$$$. You must choose in which order they are going to perform on stage.

You have $$$m$$$ friends and each of them has a set of favourite singers. More precisely, for each $$$1\le i\le m$$$, the $$$i$$$-th friend likes singers $$$s_{i,1}, \, s_{i, 2}, \, \dots, \,s_{i, q_i}$$$.

A friend of yours is happy if the singers he likes perform consecutively (in an arbitrary order). An ordering of the singers is valid if it makes all your friends happy.

Compute the number of valid orderings modulo $$$998\,244\,353$$$.

Input format:
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1\le n,\,m\le 100$$$) — the number of singers and the number of friends correspondingly.

The $$$i$$$-th of the next $$$m$$$ lines contains the integer $$$q_i$$$ ($$$1\le q_i\le n$$$) — the number of favorite singers of the $$$i$$$-th friend – followed by the $$$q_i$$$ integers $$$s_{i,1}, \, s_{i, 2}, \, \dots, \,s_{i, q_i}$$$ ($$$1\le s_{i,1}<s_{i,2}<\cdots<s_{i,q_i}\le n$$$) — the indexes of his favorite singers.

Output format:
Print the number of valid orderings of the singers modulo $$$998\,244\,353$$$.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
Explanation of the first sample: There are $$$3$$$ singers and only $$$1$$$ friend. The friend likes the two singers $$$1$$$ and $$$3$$$. Thus, the $$$4$$$ valid orderings are:

- 1 3 2
- 2 1 3
- 2 3 1
- 3 1 2

Explanation of the second sample: There are $$$5$$$ singers and $$$5$$$ friends. One can show that no ordering is valid.

Explanation of the third sample: There are $$$100$$$ singers and only $$$1$$$ friend. The friend likes only singer $$$50$$$, hence all the $$$100!$$$ possible orderings are valid.

Explanation of the fourth sample: There are $$$5$$$ singers and only $$$1$$$ friend. The friend likes all the singers, hence all the $$$5!=120$$$ possible orderings are valid.

Example input:
3 1
2 1 3

Example output:
4

Example input:
5 5
2 1 2
2 2 3
2 3 4
2 4 5
2 1 5

Example output:
0

Editorial:
Let $$$S_i := \{s_{i,1}, \, s_{i,2}, \, \dots, \, s_{i, q_i}\}$$$. Consider the graph on the subsets $$$S_1, \, S_2, \, \dots, \, S_k$$$ such that $$$S_i$$$ is adjacent to $$$S_j$$$ if and only if $$$S_i \cap S_j \ne \varnothing, \, S_i, \, S_j$$$. Without loss of generality we can assume that the sets $$$S_1, \, S_2, \, \dots, \, S_m$$$ are distinct.
Consider a connected component $$$\mathcal C$$$ in such a graph (that is, $$$\mathcal C$$$ is a family of subsets). Let $$$P(\mathcal C) := \bigcup_{S\in\mathcal C} S$$$ be the union of all sets in $$$\mathcal C$$$. For each $$$x \in P(\mathcal C)$$$, let $$$\mathcal C_x := \{S \in \mathcal C: x \in S\}$$$. Notice that $$$\mathcal C_x = \mathcal C_y$$$ if and only if the elements $$$x, \, y$$$ belongs to exactly the same set in $$$\mathcal C$$$.
Consider the equivalence relationship on $$$P(\mathcal C)$$$ induced by the function $$$x \mapsto \mathcal C_x$$$ (i.e., $$$x \equiv y \iff \mathcal C_x = \mathcal C_y$$$).
Lemma. If $$$|\mathcal C| \ge 2$$$, there is either $$$0$$$ or exactly $$$2$$$ (one is the reversal of the other) ways to order the equivalence classes so that any subset $$$T \in \mathcal C$$$ is the union of a contiguous (in the ordering) interval of equivalence classes.
Proof. This can be proven by induction on the number of sets in $$$\mathcal C$$$. If $$$|\mathcal C| = 2$$$, assume $$$\mathcal C = \{S_1, \, S_2\}$$$. The possible values of $$$\mathcal C_x$$$ are $$$\{S_1\}$$$, $$$\{S_2\}$$$, $$$\{S_1, \, S_2\}$$$. For sure the equivalence class corresponding to $$$\{S_1, \, S_2\}$$$ is nonempty and, without loss of generality, we may also assume that the equivalence class corresponding to $$$\{S_1\}$$$ is nonempty. Then the valid orderings are exactly $$$\{S_1\}\ - \ \{S_1, \, S_2\}\ - \ \{S_2\}$$$ and its reversal.
Now, assume that $$$|\mathcal C| \ge 3$$$. Take $$$S \in \mathcal C$$$ so that $$$\mathcal C' := \mathcal C \setminus \{S\}$$$ is still connected. Notice that the equivalence classes induced by $$$\mathcal C'$$$ may be less refined than those induced by $$$\mathcal C$$$ (moreover, the elements in $$$S \setminus P(\mathcal C')$$$ are not even considered). If already there is no good ordering of the equivalence classes induced by $$$\mathcal C'$$$, then the same holds for the equivalence classes induced by $$$\mathcal C$$$.
Otherwise, by induction, we may assume that there is a unique (up to reversal) ordering of the equivalence classes induced by $$$\mathcal C'$$$. Let $$$Z_1, \, Z_2, \, \dots, \, Z_k$$$ be the equivalence classes induced by $$$\mathcal C'$$$ on $$$P(\mathcal C')$$$ in the correct order. What changes when we consider also the set $$$S$$$? Each $$$Z_i$$$ splits into two (possibly empty) equivalence classes $$$Z_i' := Z_i \cap S$$$ and $$$Z_i' ' := Z_i \setminus S$$$. Moreover, we have to take care of the (possibly empty) new equivalence class $$$Z_0 := S \setminus P(\mathcal C')$$$.
Consider the set of indices $$$I$$$ so that $$$i \in I$$$ if and only if both sets $$$Z_i \cap S$$$ and $$$Z_i \setminus S$$$ are nonempty. Let us consider various cases:
• If $$$I=\varnothing$$$, then there is a valid ordering if and only if the set $$$\{1 \le i \le k: Z_i \cap S \ne \varnothing\}$$$ is a prefix or a suffix of $$$\{1,2,\dots,k\}$$$ or it is a contiguous interval and $$$Z_0=\varnothing$$$.
• If $$$|I| \ge 3$$$, then there is no good ordering.
• If $$$|I| = 2$$$, assume that $$$I= \{l, \, r\}$$$ and $$$l < r$$$. Then there is a valid ordering if and only if the set $$$\{1 \le i \le k: Z_i \cap S \ne \varnothing\}$$$ coincides with $$$[l, \, r]$$$ and $$$Z_0 = \varnothing$$$. In such case, the unique valid ordering (up to reversal) is given by: $$$$$$ Z_1, \, Z_2, \, \dots, \, Z_{l - 1}, \, Z_l' ', \, Z_l', \, Z_{l + 1}, \, \dots, \, Z_{r - 1}, \, Z_r', \, Z_r' ', \, Z_{r+1}, \, \dots, \, Z_n. $$$$$$
• If $$$|I| = 1$$$, assume that $$$I = \{t\}$$$. Then there is a valid ordering if and only if the set $$$\{1 \le i \le k: Z_i \cap S \ne \varnothing\}$$$ coincides with $$$[1, \, t]$$$ or $$$[t, \, k]$$$; or if such set is $$$\{t\}$$$ and also $$$Z_0$$$ is empty. In the first case (the other cases are analogous), the unique valid ordering (up to reversal) is given by: $$$$$$ Z_0, \, Z_1, \, Z_2, \, \dots, \, Z_{t - 1}, \, Z_t', \, Z_t' ', \, Z_{t + 1}, \, \dots, \, Z_k. $$$$$$
The lemma teaches us how to handle a single component (of course, one has to compute also the number of possible orderings of each equivalence class, which is just the factorial of its size). What about the interaction between components?
It is not hard to check that if $$$\mathcal C, \, \mathcal D$$$ are two distinct connected components then either $$$P(\mathcal C) \cap P(\mathcal D) = \varnothing$$$ or $$$P(\mathcal C) \subseteq P(\mathcal D)$$$ or $$$P(\mathcal D) \subseteq P(\mathcal C)$$$. Moreover, if $$$P(\mathcal C) = P(\mathcal D)$$$ then either $$$\mathcal C$$$ or $$$\mathcal D$$$ contains only one subset. Let us consider the forest on the connected components such that $$$\mathcal C$$$ is an ancestor of $$$\mathcal D$$$ if and only if $$$P(\mathcal D) \subseteq P(\mathcal C)$$$ (if $$$P(\mathcal C) = P(\mathcal D)$$$ then we require additionally that $$$\mathcal C$$$ contains only one subset). It is not hard to check that this ancestorship is induced by a forest. By adding (if necessary) to the initial family the subset $$$S_{k + 1} = \{1, \, 2, \, \dots, \, n\}$$$, we may assume that this forest is a tree.
The number of valid permutations is given by the product of the contributions of each connected component $$$\mathcal C$$$. The contribution of a connected component $$$\mathcal C$$$ is the product of the contributions of the equivalence classes of $$$P(\mathcal C)$$$ (and, if there is more than one equivalence class, a factor $$$2$$$). Given an equivalence class $$$E$$$ of $$$P(\mathcal C)$$$, its contribution is the factorial of $$$$$$ |P(\mathcal C)| - \sum_{\substack{\mathcal D \in \text{sons}(\mathcal C) \\ P(\mathcal D)\subseteq E}} \big(|P(\mathcal D)|-1\big). $$$$$$ In other words, the problem is completely independent for different connected components up to collapsing the smaller connected components to a single element.
Complexity: $$$O\left(\frac{k^2n}{64}\right)$$$ (using bitsets to store the subsets and implementing everything naïvely).