XOR Graph Connectivity Subset Count

Given s graphs, each with the same set of n nodes numbered from 1 to n, we define the XOR of two graphs as follows:

For any two nodes \(u\) and \(v\), the edge \((u,v)\) appears in \(G_1 \oplus G_2\) if and only if the total number of appearances of \((u,v)\) in \(G_1\) and \(G_2\) is exactly 1. In other words, using modulo 2 arithmetic, \[ G = G_1 \oplus G_2 \quad \text{where} \quad G(u,v) = (G_1(u,v) + G_2(u,v)) \bmod 2. \]

Now, you are given s graphs \(G_1,G_2,\dots,G_s\). For any non-empty subset of these graphs, define its XOR as the graph obtained by taking the XOR of all graphs in the subset. Your task is to count how many non-empty subsets have an XOR graph that is connected. A graph is connected if there is a path between any pair of nodes.

inputFormat

The first line contains two integers n and s, representing the number of nodes and the number of graphs respectively.

For each of the next s blocks:

• The first line of the block contains an integer m, the number of edges in the graph.
• Then follow m lines, each containing two integers \(u\) and \(v\) (1-indexed) denoting an undirected edge between nodes \(u\) and \(v\). There are no self-loops and each edge appears at most once in each graph.

outputFormat

Output a single integer: the number of non-empty subsets of the given graphs whose XOR is connected.

sample

3 2
2
1 2
2 3
1
1 3

2