Expected Number of Perfect Matchings

Consider a bipartite graph with two sets of vertices (left and right) each having \(n\) vertices. The only possible edges in the graph are given via groups. Each edge either does not appear at all (if it is not assigned to any group), or belongs to exactly one group. There are exactly three kinds of groups:

1. Type 0. The group has exactly one edge and that edge appears with probability \(50\%\).
2. Type 1. The group has exactly two edges. These two edges appear together with probability \(50\%\) and do not appear at all with probability \(50\%\). (Thus, if a perfect matching uses any edge from this group, the contribution is \(0.5\); note that even if both edges are used, the probability factor remains \(0.5\).)
3. Type 2. The group has exactly two edges. Exactly one of these edges appears with probability \(50\%\) for each edge. (Thus if a perfect matching uses an edge from a Type 2 group, the contribution is \(0.5\), but if a matching would use both edges from a Type 2 group then it is impossible.)

The groups act independently. That is, for each group the event of its edges appearing happens independently of the events in the other groups. For an edge that belongs to a group, if the group’s event causes the edge to appear then it is present in the graph; if not, it is absent. Edges that do not belong to any group will definitely not appear.

A perfect matching is a set of \(n\) edges such that each left vertex is matched with a distinct right vertex. Your task is to compute the expected number of perfect matchings in the random graph generated by the above process.

Mathematically, if a perfect matching \(M\) uses an edge from some group \(g\) then it contributes a factor as follows:

• If \(g\) is of Type 0, the edge contributes a factor of \(0.5\).
• If \(g\) is of Type 1, whether one or both of its edges are used, the group contributes a factor of \(0.5\) (if at least one edge is used).
• If \(g\) is of Type 2 and exactly one edge is used then it contributes \(0.5\); if both are used (which is impossible in a matching) then the matching is invalid.

Therefore, the expected number is given by summing over all perfect matchings \(M\) the product over groups \(g\) (appearing in \(M\)) of \(0.5\). In other words, if for a given perfect matching the set of groups that contribute is \(S\) then its probability is \((0.5)^{|S|}\), and if any Type 2 group contributes two edges then the matching does not occur.

You are to compute this expected value as a floating–point number. It is guaranteed that \(n\) and the number of groups are small enough so that a solution using state–compression dynamic programming is feasible.

inputFormat

The first line contains two integers \(n\) and \(m\), where \(n\) (\(1 \le n \le 10\)) is the number of vertices in each part, and \(m\) is the number of groups.

Each of the next \(m\) lines describes a group. A group description begins with an integer \(t\) (the type of the group, which is \(0\), \(1\), or \(2\)). If \(t = 0\), it is followed by an integer \(1\) and then 2 integers \(u\) and \(v\), indicating an edge from left vertex \(u\) to right vertex \(v\) (vertices are 1-indexed). If \(t = 1\) or \(t = 2\), it is followed by an integer \(2\) and then 4 integers representing two edges: \(u_1\) \(v_1\) and \(u_2\) \(v_2\).

Note: Edges not belonging to any group will never appear.

outputFormat

Output a single floating–point number: the expected number of perfect matchings. Answers within an absolute or relative error of \(10^{-6}\) will be accepted.

sample

1 1
0 1 1 1

0.5