Description

Someone is playing a very magical game. In this game, there is a bipartite graph with $n$ vertices on the left and $n$ vertices on the right, and edges appear randomly according to certain rules.

To describe these rules, the edges are partitioned into several groups. Each edge either belongs to exactly one group, or to no group at all (such edges will never appear).

There are exactly the following three types of groups:

0. Each such group contains exactly one edge, and that edge appears with probability $50\%$.
1. Each such group contains exactly two edges; the two edges either both appear with probability $50\%$, or both do not appear with probability $50\%$.
2. Each such group contains exactly two edges; exactly one of the two appears, and each has probability $50\%$ of appearing.

Edge appearances from different groups are mutually independent.

Now that the grouping and types of edges are given, one wants to know the expected number of perfect matchings. Can you help her solve this problem?

Input Format

Read from standard input.

The first line contains two integers $n$ and $m$, denoting the number of vertices on each side of the bipartite graph and the number of edge groups. We use $(a,b)$ (where $1 \le a, b \le n$) to denote an edge whose left endpoint is the $a$-th vertex on the left and whose right endpoint is the $b$-th vertex on the right.

The next $m$ lines each describe one group. The first number $t$ denotes the group type, where $t=0$ means a one-edge group, $t=1$ means the first kind of two-edge group, and $t=2$ means the second kind of two-edge group. If $t=0$, then the next two integers $a_1, b_1$ specify the single edge in the group. Otherwise, the next four integers $a_1, b_1, a_2, b_2$ specify that the two edges in the group are $(a_1, b_1)$ and $(a_2, b_2)$. It is guaranteed that each edge appears at most once.

Output Format

Output to standard output.

Suppose the expected number of perfect matchings is $E$. Output one line:

It can be seen that the above expression is an integer.

2 2
1 2 1 2 2
2 1 2 1 1

2

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

7

4 9
2 4 1 4 2
1 3 2 1 4
2 2 1 4 4
2 3 4 1 1
2 4 3 2 4
2 2 2 3 1
0 1 3
0 3 3
1 2 3 1 2

20

Hint

Definition Explanation.

If you are familiar with the definitions of perfect matching and expectation, you may skip this part.

For a bipartite graph with $n$ vertices on each side, a perfect matching is a matching consisting of $n$ edges with no shared endpoints.

Two perfect matchings are different if and only if they contain at least one different edge. The number of perfect matchings of a bipartite graph is defined as the number of pairwise distinct perfect matchings that can be found in this graph.

In this problem, edges appear randomly, so the number of perfect matchings is a random variable. The expectation of a (discrete) random variable $X$ is defined as the probability-weighted average of all possible values of $X$, i.e.,

where $V(X)$ denotes the set of all possible values of $X$, and $P[X = x]$ denotes the probability that $X$ takes the value $x$.

Constraints.

• For $5\%$ of the testdata, $n \le 5$.
• For another $5\%$ of the testdata, $n \le 8$.
• For another $10\%$ of the testdata, $n \le 10$.
• For another $15\%$ of the testdata, only $t = 0$ occurs.
• For another $5\%$ of the testdata, only $t = 0$ occurs and $m = n^2$, i.e., the graph is a complete graph.
• For another $20\%$ of the testdata, only $t = 0$ or $t = 1$ occurs.
• For another $20\%$ of the testdata, only $t = 0$ or $t = 2$ occurs.
• For $100\%$ of the testdata, $n \le 15$.

Translated by ChatGPT 5