All the spanning trees

counting linear algebra number theory graph matrix

The city services want to know how much “spare” a district's street network has: in how many ways some of the streets can be left open so that there is still a way between any two crossings, but no loop is left. Each such set of streets is a spanning tree of the graph. Two streets between the same crossings count as different, and so do trees that differ in the choice of one of them.

For a district of a few dozen crossings the answer easily goes beyond 64 bits, and for the complete graph on 30 vertices it has 42 digits. The exact number is needed.

Input

The first line holds the number of crossings n and the number of streets m (1 ≤ n ≤ 80, 0 ≤ m ≤ 1000). Each of the following m lines holds two different crossing numbers u and v (1 ≤ u, v ≤ n) joined by a street. There can be several streets between one pair of crossings.

Output

One number, the count of spanning trees. If the graph is disconnected, there are none, and the answer is 0; a graph of one vertex has exactly one tree, without streets.

Examples

Example 1

Input

Output

Limits

Time · Python: 8000 ms
Time · Go: 2000 ms
Memory: 256 MB
Judging: 11 tests

Walkthrough

Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.

1Hint 1

Trying subsets of streets is pointless: there are 2^m of them. The number of spanning trees is given by Kirchhoff's formula: the determinant of the matrix with vertex degrees on the diagonal and −1 in the cells (u, v) and (v, u) for each street uv, without one row and the same column. How do you compute a determinant exactly if it has a hundred digits?

2Hint 2

Gaussian elimination in floating point gives only the first 15–16 digits. The determinant is an integer, so it can be computed modulo several primes. How many moduli are needed to recover the answer uniquely?

3The idea

Compute the determinant modulo primes p₁, p₂, … by Gaussian elimination, with division replaced by multiplication by the inverse, and recover the answer from the residues by Garner's algorithm. You need enough moduli for their product to exceed the answer, and a simple observation gives the bound: there are no more trees than the product of the degrees of all vertices but one. Each tree is uniquely determined by which edge leads from each vertex towards the root.

4Walkthrough

Build Kirchhoff's matrix L and cross out the last row and the last column. The bound B is the product of the degrees of vertices 1…n − 1 (if some degree is zero, the graph is disconnected, the bound is zero and the answer is zero). Take prime moduli from the top down until their product exceeds B, and for each compute the determinant: find a non-zero entry in the column, swap rows (the sign of the determinant changes), multiply the determinant by the pivot and subtract the row multiplied by a_rc·a_cc⁻¹ from the rows below.

In the Python reference the moduli are primes slightly below 2⁶¹: long arithmetic is free, and the longer the modulus, the fewer of them are needed, here at most seven. In Go the moduli are below 2³¹: then the product of two residues fits in uint64, and math/big is needed only to assemble the answer and the bound. If the graph is disconnected, the determinant is zero modulo any modulus, and Garner returns zero.

You can also do without moduli: Bareiss's method computes the determinant of an integer matrix in integers, dividing exactly by the previous pivot, and Python's fractions reduce themselves. At these sizes both ways fit in the limit; the article has a measurement of which is faster where.

4+Solution

5Complexity

O(n³) operations per modulus; O(n log D / log p) moduli, where D is the largest degree. Assembly by Garner's algorithm is O(k²) for k moduli.

6Common mistakes

Floating-point numbers. For the complete graph on 30 vertices the answer is 30²⁸, 42 digits, and a double keeps sixteen of them. Rounding at the end does not help.
Too few moduli. If the moduli are taken “by eye”, Garner returns the remainder of the answer modulo their product: a plausible and wrong number.
Multiple streets. Two streets between one pair of crossings give −2 in the cell, not −1, and the vertex degree grows by two. The answer for two vertices with a thousand streets between them is 1000.
One vertex. The matrix without a row and a column is empty, and its determinant is 1. It is handier to deal with this case separately at once.

Algorithms behind it

NUM Algorithm Chinese remainder theorem A number from its residues modulo several moduli: Garner's algorithm and exact computation over many primes. O(k²) operations on machine numbers 2 problems NUM Algorithm Gaussian elimination A linear system by elimination: the pivot, LU, conditioning, sparse matrices and fill-in. O(n³): about n³/3 multiplications for the forward pass 2 problems