Series-Parallel Resistance Computation

Little Y is a brilliant girl but she only knows how to compute the effective resistance between two nodes in a resistor network by using series and parallel combinations. Given an undirected resistor network with n nodes and m edges (each edge represents a resistor), your task is to count how many pairs of distinct nodes \( u,v \) have the property that the effective resistance between them can be computed by series-parallel reductions.

Formally, for any two distinct nodes \( u,v \) in the graph, define \( S \) as the union of all nodes appearing on any simple path (i.e. a path not repeating any node) from \( u \) to \( v \). Let \( G[S] \) be the subgraph of the original graph induced by \( S \) (that is, it contains all edges of the original graph with both endpoints in \( S \)). If \( S \) is nonempty (which means \( u \) and \( v \) are connected) and \( G[S] \) is a two-terminal series–parallel graph with \( u \) and \( v \) as its two terminals, then the effective resistance between \( u \) and \( v \) can be computed by using series and parallel combinations.

A two‐terminal graph with distinct endpoints \( s \) and \( t \) is defined as follows:

• A graph consisting of two nodes connected by a single edge is two‐terminal.
• If \( X \) and \( Y \) are two-terminal graphs, then the parallel composition of \( X \) and \( Y \) is obtained by merging their respective sources and their respective sinks.
• If \( X \) and \( Y \) are two-terminal graphs, then the series composition of \( X \) and \( Y \) is obtained by merging the sink of \( X \) with the source of \( Y \).
• A graph formed by a sequence of series and parallel compositions starting from graphs consisting of a single edge is called a two-terminal series–parallel graph.

Given the resistor network, count the number of distinct pairs \( u,v \) (with \( u\neq v \)) for which the effective resistance between \( u \) and \( v \) can be computed using only series and parallel combinations.

inputFormat

The first line contains two positive integers \( n \) and \( m \) (\( 1\le n\le 10 \), \( 0\le m\le \frac{n(n-1)}{2} \)) — the number of nodes and edges in the resistor network.

Each of the following \( m \) lines contains two integers \( u \) and \( v \) (\( 1\le u,v \le n \), \( u\neq v \)), representing an undirected edge connecting nodes \( u \) and \( v \).

outputFormat

Output a single integer representing the number of node pairs \( (u,v) \) (with \( u\neq v \)) for which the effective resistance can be computed using series and parallel reductions.

sample

3 3
1 2
2 3
1 3

3