#include <iostream.h>
#include <iomanip.h>
#include <NTL/ZZ.h>
#include <NTL/mat_ZZ.h>

/**********************************************************

  Problem: In how many ways can the regular polyhedra be unfolded?

------------------------------------------------------------

  Complexity of a graph G
    = the number of labled spanning trees of the graph G
    = c(G)

  Compute c(G) for the graphs of the regular polyhedra.
  There are the following two formulars to do so.

  (1)  adj(F) = adj(D - B) = c(G)*J   [Matrix-Tree-Theorem, (Kirchhoff)]

  (2)  c(G) = det(F + J)/n^2 = det(D - B + J)/n^2

    F : Laplacian of a graph G.
    D : diagonal matrix of order n with entries d(i,i) = degree(i)
    B : adjacency matrix, b(i,j) = [vertices i and j are connected]
    J : all entries are 1.
    n : number of vertices of graph G.

  According to Horst Sachs the Matrix-Tree-Theorem is implicidly
  stated by Kirchhoff. Trent first used the determinat theorem of
  Cauchy-Binet for the proof. The text book proof is based on
  the simplifications of Hutschenreuther.

  We talk of a plane graph if a crossless embedding in the plane
  of a planar graph is already given and fixed.

  Theorem: [A. Sanders, D. V. Smith]
   Let G be a plane connected graph. If G* is the dual graph of G then

    c(G) = c(G*).

   Note that A. Sanders, D. V. Smith didn't saw the general case
   and explained it only on the example for cube<->octahedron.
   This theorem follows from the spanning tree duality. This is
   the major part of a "self-dual" proof of Euler's formula.
   Some Notation: e(G) is the number of edges of the graph G.

  Theorem A: spanning tree duality.
   If G is a connected plane graph and G* its dual then
   there is a bijection between the sets of spanning trees of G and G*.
   Let T and T* be two corresponding spanning trees then e(G) = e(T)+e(T*).

  Proof: [Aigner, Ziegler, Proofs from THE BOOK, p57]
   Let T \subset E be the edge set of a spanning tree for G, that is, of a
   minimal subgraph that connects all the vertices of G. This graph does not
   contain a cycle because of the minimality assumption.
   We now need the dual graph G* of G: to construct it, put a vertex into the
   interior of each face of G, and connect two such vertices of G* by edges
   that  correspond to common boundary edges between the corresponding faces.
   If there are several common boundary edges, then we draw several connecting
   edges in the dual graph. (Thus G* may have double edges even if the original
   graph G is simple.)
   Now consider the collection T* \subset E* of edges in the dual graph that
   corresponds to edges in E\T. The edges in T* connect all the faces, since
   T does not have a cycle; but also T* does not contain a cycle, since 
   otherwise it would separate some vertices of G inside the cycle from
   vertices outside (and this cannot be, since T is a spanning subgraph,
   and the edges of T and of T* do not intersect). Thus T* is a spanning
   tree for G*.  qed

  Theorem B: Euler's formula.
   If G is a connected plane graph with v vertices, e edges and f faces, then
     v - e + f = 2.

  Proof: [Aigner, Ziegler, Proofs from THE BOOK, p57]
   For every tree T the number of vertices is one larger than the number of 
   edges. This yields v(G) = v(T) = e(T)+1, while for the corresponding dual
   spanning tree T* is yields f(G) = v(G*) = v(T*) = e(T*)+1. Adding both
   equations we get v(G) + f(G) = e(T)+1 + e(T*)+1 = e(G) + 2.  qed


  Some numbers for Platonic solids:

  c(tetrahedron) = c(K_4) = 4^2 = 16
   spanning trees =  2
     the spanning trees are a K_1,3 and a P_4 with 
     symmetries groups S_3 and Z_2 (the embedded P_4).
     So c = 16 = o(S_4)/o(S_3) + o(S_4)/o(Z_2) = 4 + 12.

  c(cube) = 384
   spanning trees = c/48 + symmetrical spanning trees/2
                  =  8  +  6/2  =  11

  c(dodecahedron) = 5184000
   spanning trees = c/o(S_5) + symmetrical spanning trees/2
                  = 43200 + symmetrical spanning trees/2
                  = 43200 + 360/2  =  43380
   This has been computed also by
   [Helmut Postl] and [P. Light and D. Singmaster].
  
  c(rhombic-dodecahedron) = 331776
   spanning trees = c/48  (there are no symmetric trees)
		  = 6912

  c(triangular prism) = 75
   spanning trees = 8  (the unfolding of two trees are equal)
   The hexiamond 'Sphinx' build the bipyramid in two ways.


  References:

  - Martin Aigner, G"unter M. Ziegler;
    Proofs from THE BOOK,
    Springer, Berlin, 1998
    - Chapter 22: Cayley's formula for the number of trees.
      Second Proof (Linear Algebra) [Matrix-Tree-Theorem]
    - Chapter 10: Three applications of Euler's formula.

  - F. Buekenhout, M. Parker;
    The Number of Nets of the Regular Convex Polytopes in Dimension <= 4,
    Disc. Math. 186 (1998) 69-94

  - S. Chaiken;
    A combinatorial proof of the all minors matrix tree theorem,
    SIAM J. Alg. Disc. Meth. 3 (1982) 319-329

  - Peter R. Cromwell;
    Polyhedra,
    Cambridge Univ. Press, 1997
    - Several Proofs of Euler's Thm.
      Von Strauds's dual trees proof.

  - Brualdi, Ryser;
    Combinatorial Matrix Theory,
    Cambridge Univ. Press, 1991
    Sect. 2.5 The Laplacian Matrix of a Graph

  - N. P. Dolbilin;
    Rigidity of convex polyhedrons,
    Quantum 9:1 (Sep/Oct. 1998) 8-13
    - regular development: an unfolding without self-intersection
      e.g. a trucated regular tetrahedron has irregular developments
      (Quantum (Nov/Dec. 1997) 26, 48-49 M219: Developing a polyhedron)

  - Komei Fukuda;
    (a) Does every convex polytope admit a non-selfoverlapping unfolding?
    (b) Does every convex polytope admit an unambiguous unfolding?
    Tagungsbericht 20/1997 p27-28, Discrete Geometry, Oberwolfach
    http://www.ifor.math.ethz.ch/staff/fukuda/unfold_home/unfold_open.html

  - Frank Harary;
    Graph Theory,
    Addison Wesley, 1969
    (german: Graphentheory, Oldenbourg, 1974)
    Chapter 13: matrices 
        Theorem  13.4 Matrix-Tree-Theorem
        Exercise 13.5 Tree Polynomial

  - Heinrich Hemme;
    Das Hexeneinmaleins,
    to appear, 2000
    Problem 61: Hexaedernetze (folding the bipyramide)
    Problem 62: Wuerfelnetze (folding the cube)
    Problem 63: Ikosaedernetze (folding the icosahedron)

  - H. Hutschenreuther;
    Ein einfacher Beweis des Matrix-Ger"ustsatzes der Netzwerktheorie,
    Wiss. Z. TH Ilmenau (1967), H 4, Teil 2, 403-404

  - G. Kirchhoff;
    "Uber die Aufl"osung der Gleichungen, auf welche man bei
    der Untersuchung der linearen Verteilung galvanischer 
    Str"ome gef"uhrt wird.
    Annalen der Physik und Chemie 72 (1847) 497-508

  - P. Light, D. Singmaster;
    The nets of the regular polyhedra.
    (draft, witten pre 1993, not published until 1999)
    (There are 43380 nets for the dodecahedron and icosahedron.
    They counted the number in three ways.)

  - E. Keith Lloyd, Guy H. F. Meredith;
    Enumeration of Face Nets for Pyramids, Prisms and Antiprisms,
    21p, (refereed but unpublished)
    (fig 1 shows an selfoverlapping onfolding of a 30-prism
     which is attributed to an anonymous referee.
     Explains why the 3-prism has 9 different unfoldings but
     its dual (a bipyramid) has only 8 different.)

  - Russell Merris;
    Laplacian matrices of graphs: a survey,
    Lin. Algebra. Appl. 197 (1994), 143-176.

  - Georg Polya;
    Guessing and Proving,
    Two Year College Mathematics Journal 9:1 (Jan 1978) 21-27
    - Discussion of Euler's theorem, E = F + V - 2

  - Helmut Postl;
    Letter to Heinrich Hemme, (Wien) 5. June 1992
    (Found 43380 nets for the dodecahedron and icosahedron.
     Used the Matrix-Tree-Theorem. Postl used excactly the
     same method than I.)

  - Horst Sachs;
    Einf"uhrung in die Theorie der endlichen Graphen, Teil 1,
    Teubner Verlag, Leipzig, 1970, Math-Naturwissenschaftliche Bibliothek 43
    Sect. 1.5. Der Satz von Kirchhoff-Trent

  - A. Sanders, D. V. Smith;
    Nets of the octahedron and the cube.
    Mathematics Teaching 42 (Spring 1968) 60-63
    (Finds all 11 nets for the octahedron an shows a duality with the cube.)

  - David Singmaster;
    Sources in Recreational Mathematics,
    An Annotated Bibliography, 6th Pre. Ed., Nov. 1993
    Part I, Sect. 6.AA Nets of Polyhedra, p 195
    (list references: [A. Sanders, D. V. Smith], [P. Light, D. Singmaster])

  - Dennis Stanton, Dennis White;
    Constructive Combinatorics,
    Springer Verlag, 1986
    (Sect. 4.4: The Matrix Tree Theorem 
     They give the proof [Chaiken] with sign reversing involutions)

  - H. Trent;
    A note on the enumeration and listing of all possible trees
    in a connected linear graph,
    Proc. Nat. Acad. Sci. USA 40 (1954) 1004-1007
------------------------------------------------------------
  The origin of Theorem A: spanning tree duality.

  From: "Guenter M. Ziegler" <ziegler@math.TU-Berlin.DE>
  Date: Thu, 3 Jun 1999 08:34:09 +0200 (MET DST)
  Subject: Re: Euler's characteristic
  
  
  I saw this proof on David Eppstein's ``Geometry Junkyard'', where
  Fifteen Proofs are given of Euler's formula,
  at http://www.ics.uci.edu/~eppstein/junkyard/euler/
  the first one of which is the ``interdigitating trees''
  proof. According to Eppstein, this proof (first)
  appears in Sommerville's ``An Introduction to the Geometry
  of N dimensions'' (London, 1929; Dover reprint 1958),
  and is there attributed to van Staudt.
  However, I have not looked up either of these two sources.
  (van Staudt is hard to read -- I've looked at that
  long ago for a different topic. Sommerville should be readable.)
------------------------------------------------------------

  Symmetrical spanning trees of the cube:
    Draw the cube standing on one edge.
    If we fix the edge of symmetry all symmetric spanning trees 
    are generatad twice.

               |      The 0-7 (or 3-4) connection is center of symmetry
               3      of the spanning trees. The antipode of a vertex u
              / \      is 7-u. Partition the vertices into two sets,
             /   \      such that antipodal pair are in different sets.
            1     2     The antipodals in this cube graph are placed
            |\   /|     rotational symmetric to 0-7.
            | \ / |
            |  0  |
            |  +  |
            |  7  |
            | / \ |
            |/   \|
            5     6
             \   /
              \ /
               4
               |

  spanning trees with rotaional symmetry on 0-7 (or 3-4):

  0 Subgraph :  0  1  2  3 :       4 spanning trees

       3       3       3       3
      / \       \     /       / \
     1   2   1   2   1   2   1   2
        /     \ /     \ /     \   
       0       0       0       0  
       +       +       +       +  
       7       7       7       7  
      /       / \     / \       \ 
     5   6   5   6   5   6   5   6
      \ /     \         /     \ /
       4       4       4       4

  2 Subgraph :  0  2  3  6 :       1

       3
        \
     1   2
     |  /|
     | 0 |
     | + |                        
     | 7 | 
     |/  |
     5   6
      \  
       4

  3 Subgraph :  2  3  6  7 :       1

       3
        \
     1   2
     |\  |
     | 0 |
     | + |                        
     | 7 | 
     |  \|
     5   6
      \  
       4

  4 Subgraph :  0  1  3  5 :       1

       3
      /  
     1   2
     |\  |
     | 0 |
     | + |                        
     | 7 | 
     |  \|
     5   6
        /
       4

  5 Subgraph :  1  3  5  7 :       1

       3
      /  
     1   2
     |  /|
     | 0 |
     | + |                        
     | 7 | 
     |/  |
     5   6
        /
       4

  spanning trees with reflection symmetry on 0-7 (or 3-4):

  0 Subgraph :  0  1  2  3 :       4 spanning

       3       3       3       3
      / \       \     /       / \
     1   2   1   2   1   2   1   2
        /     \ /     \ /     \   
       0       0       0       0  
       +       +       +       +  
       7       7       7       7  
        \     / \     / \     /   
     6   5   6   5   6   5   6   5
      \ /       /     \       \ /
       4       4       4       4

  There is no spanning tree having left-right reflection symmetry.

       |
       3
      / \
     1   2    A left-right symmetry transforms
     |\ /|
     | 0 |    1 <-> 2 and 5 <-> 6
     | | |
     | 7 |    The points 0, 3, 4, and 7 remain fixed.
     |/ \|
     5   6
      \ /
       4
       |

  Assume the is a spanning tree with a left-right symmetry.
  Then we have a shortest path in this tree from 0 to 3.
  Now we can reflect this path and get a second shortest path 
  between 0 and 3. In a tree the shortest path between two
  vertices is unique. So the two path must be the same.
  But then all points of the path must be fixpoints of the 
  symmetry. But the induced subgraph of the fixpoints {0, 3, 4, 7}
  is not connected. The vertices 0 and 3 are in different 
  components. Therefore no left-right symmetric spanning tree 
  is possible.

  There is no spanning tree having threefold symmetry.
  Such a symmetry must be at a vertex, but the three
  subtrees round a vertex can't be of equal size
  as 3 do not divide 8-1 = 7.

------------------------------------------------------------

       3       3       3       3
      / \     / \     / \     / \
     1   2   1   2   1   2   1   2
     |\ /|   |\ /|   |\ /|   |\ /|
     | 0 |   | 0 |   | 0 |   | 0 |
     | | |   | | |   | | |   | | |
     | 7 |   | 7 |   | 7 |   | 7 |
     |/ \|   |/ \|   |/ \|   |/ \|
     5   6   5   6   5   6   5   6
      \ /     \ /     \ /     \ /
       4       4       4       4

------------------------------------------------------------

  The graph of the dodecahedon standing on edge 0-19
  which is labled with rotational symmetry.
  The antipode of vertex u is vertex 19-u.

                            |                             
                   7--------9--------8                    
                   |\               /|                    
                   | \             / |                    
                   |  \           /  |                    
                   |   \         /   |                    
                   |    \       /    |                    
                   |     \     /     |                    
                   |      3---4      |                    
                   |      |   |      |                    
                   |      1   2      |                    
                   |     / \ / \     |                    
                   |    /   0   \    |                    
                   6---5    +   14--13                    
                   |    \  19   /    |                    
                   |     \ / \ /     |                    
                   |     17  18      |                    
                   |      |   |      |                    
                   |     15--16      |                      
                   |     /     \     |                    
                   |    /       \    |                    
                   |   /         \   |                    
                   |  /           \  |                    
                   | /             \ |                    
                   |/               \|                    
                  11-------10-------12                     
                            |                             
                                                          
  spanning trees with rotaional symmetry on 0-19 (or 9-10):

            vertices of the induced subgraph |  spanning trees
--------------------------------------------+-----------------
  0 Subgraph :  0  1  2  3  4  5  6  7  8  9 :     108
  4 Subgraph :  0  1  3  4  5  6  7  8  9 17 :      24
  5 Subgraph :  1  3  4  5  6  7  8  9 17 19 :      24
  7 Subgraph :  3  4  5  6  7  8  9 17 18 19 :       5
 15 Subgraph :  4  5  6  7  8  9 16 17 18 19 :       1
 20 Subgraph :  0  1  3  5  6  7  8  9 15 17 :       5
 21 Subgraph :  1  3  5  6  7  8  9 15 17 19 :       5
 23 Subgraph :  3  5  6  7  8  9 15 17 18 19 :       1
 28 Subgraph :  0  1  5  6  7  8  9 15 16 17 :       1
 29 Subgraph :  1  5  6  7  8  9 15 16 17 19 :       1
 31 Subgraph :  5  6  7  8  9 15 16 17 18 19 :       5
 32 Subgraph :  0  1  2  3  4  6  7  8  9 14 :      24
 34 Subgraph :  0  2  3  4  6  7  8  9 14 18 :       5
 35 Subgraph :  2  3  4  6  7  8  9 14 18 19 :       5
 42 Subgraph :  0  2  4  6  7  8  9 14 16 18 :       1
 43 Subgraph :  2  4  6  7  8  9 14 16 18 19 :       1
 64 Subgraph :  0  1  2  3  4  5  7  8  9 13 :      24
 68 Subgraph :  0  1  3  4  5  7  8  9 13 17 :       5
 69 Subgraph :  1  3  4  5  7  8  9 13 17 19 :       5
 84 Subgraph :  0  1  3  5  7  8  9 13 15 17 :       1
 85 Subgraph :  1  3  5  7  8  9 13 15 17 19 :       1
 96 Subgraph :  0  1  2  3  4  7  8  9 13 14 :     108
 98 Subgraph :  0  2  3  4  7  8  9 13 14 18 :      24
 99 Subgraph :  2  3  4  7  8  9 13 14 18 19 :      24
103 Subgraph :  3  4  7  8  9 13 14 17 18 19 :       5
106 Subgraph :  0  2  4  7  8  9 13 14 16 18 :       5
107 Subgraph :  2  4  7  8  9 13 14 16 18 19 :       5
111 Subgraph :  4  7  8  9 13 14 16 17 18 19 :       1
119 Subgraph :  3  7  8  9 13 14 15 17 18 19 :       1
122 Subgraph :  0  2  7  8  9 13 14 15 16 18 :       1
123 Subgraph :  2  7  8  9 13 14 15 16 18 19 :       1
127 Subgraph :  7  8  9 13 14 15 16 17 18 19 :       5
192 Subgraph :  0  1  2  3  4  5  8  9 12 13 :       5
196 Subgraph :  0  1  3  4  5  8  9 12 13 17 :       1
197 Subgraph :  1  3  4  5  8  9 12 13 17 19 :       1
200 Subgraph :  0  1  2  4  5  8  9 12 13 16 :       1
207 Subgraph :  4  5  8  9 12 13 16 17 18 19 :       1
220 Subgraph :  0  1  5  8  9 12 13 15 16 17 :       1
221 Subgraph :  1  5  8  9 12 13 15 16 17 19 :       1
223 Subgraph :  5  8  9 12 13 15 16 17 18 19 :       5
224 Subgraph :  0  1  2  3  4  8  9 12 13 14 :      24
226 Subgraph :  0  2  3  4  8  9 12 13 14 18 :       5
227 Subgraph :  2  3  4  8  9 12 13 14 18 19 :       5
231 Subgraph :  3  4  8  9 12 13 14 17 18 19 :       1
232 Subgraph :  0  1  2  4  8  9 12 13 14 16 :       5
234 Subgraph :  0  2  4  8  9 12 13 14 16 18 :      24
235 Subgraph :  2  4  8  9 12 13 14 16 18 19 :      24
239 Subgraph :  4  8  9 12 13 14 16 17 18 19 :       5
248 Subgraph :  0  1  2  8  9 12 13 14 15 16 :       1
250 Subgraph :  0  2  8  9 12 13 14 15 16 18 :       5
251 Subgraph :  2  8  9 12 13 14 15 16 18 19 :       5
255 Subgraph :  8  9 12 13 14 15 16 17 18 19 :      24
256 Subgraph :  0  1  2  3  4  5  6  7  9 11 :      24
260 Subgraph :  0  1  3  4  5  6  7  9 11 17 :       5
261 Subgraph :  1  3  4  5  6  7  9 11 17 19 :       5
263 Subgraph :  3  4  5  6  7  9 11 17 18 19 :       1
272 Subgraph :  0  1  2  3  5  6  7  9 11 15 :       5
276 Subgraph :  0  1  3  5  6  7  9 11 15 17 :      24
277 Subgraph :  1  3  5  6  7  9 11 15 17 19 :      24
279 Subgraph :  3  5  6  7  9 11 15 17 18 19 :       5
280 Subgraph :  0  1  2  5  6  7  9 11 15 16 :       1
284 Subgraph :  0  1  5  6  7  9 11 15 16 17 :       5
285 Subgraph :  1  5  6  7  9 11 15 16 17 19 :       5
287 Subgraph :  5  6  7  9 11 15 16 17 18 19 :      24
288 Subgraph :  0  1  2  3  4  6  7  9 11 14 :       5
290 Subgraph :  0  2  3  4  6  7  9 11 14 18 :       1
291 Subgraph :  2  3  4  6  7  9 11 14 18 19 :       1
304 Subgraph :  0  1  2  3  6  7  9 11 14 15 :       1
311 Subgraph :  3  6  7  9 11 14 15 17 18 19 :       1
314 Subgraph :  0  2  6  7  9 11 14 15 16 18 :       1
315 Subgraph :  2  6  7  9 11 14 15 16 18 19 :       1
319 Subgraph :  6  7  9 11 14 15 16 17 18 19 :       5
symmetric spanning trees dodecahedron 720 (double counted)

The spanning trees of the induced subgraphs.
In the table given above four different numbers of
the spanning trees occour. They correspond to the
number of 5-cycles that the subgraph contains.

  # 5-cycles       # spanning trees      subgraph -> spanning tree
    0                     1                is a tree
    1                     5                delete one edge of the 5-cycle
    2                    24 = 5^2-1        delete two edges of the 5-cycles
    3                   108 = 5^3-3*5-2    delete three edges of the 5-cycles

------------------------------------------------------------
cubeoctahedron (dual of the rhombic dodecahedron)

                ---9---  
               |  / \  | 
               | 5-0-4 | 
               |/|/ \|\| 
               8 1   3 10
               |\|\ /|/| 
               | 7-2-6 | 
               |  \ /  | 
                --11---  

------------------------------------------------------------
triangular prism:
  The spanning trees correspond to hexiamonds.
  The following 4 hexiamonds have a vertex of order 5 or more.
  Therefore these cannot be folded to the bipyramid.

   o---o        o---o        o---o        o---o
  / \ / \      / \ /        / \ / \      / \ / \
 o---6---o    o---5---o    o---5---o    o---5---o
  \ / \ /    / \ / \ /    / \ / \      / \ / \ /
   o---o    o---o---o    o---o---o    o---o   o

  All others can be folded to the bipyramid.

  o---o---o        o                                     o---o
   \ / \ /        / \                                   / \ /
    4---4    o---4---4---o    o---o---o---o---o    o---4---o
   / \ / \    \ / \ / \ /    / \ / \ / \ / \ /    / \ / \ /
  o---o---o    o---o---o    o---o---o---o---o    o---o---o
  
      o---o        o---o            o
     / \ / \        \ / \          / \
    o---4---4---o    4---4---o    o---4---o---o---o
         \ / \ /    / \ / \ /      \ / \ / \ / \ /
          o---o    o---o---o        o---o---o---o

      o                 x    The 'Sphinx' can be folded in two 
     / \               / \   different ways to make the bipyramid.
    o---4---o     ->  o---o
   / \ / \ / \        |\ /|
  x---o---o---y       | 4 |
                      |/ \|
  The Sphinx          o---o
                       \ /
                        y

octahedra:


  o---o---o
   \ / \ / \
    o---o---o---o
         \ / \ / \
          o---o---o

  This net of a regular octahedron can be folded
  to a nonconvex octahedron (3 tetrahedra glued together).


------------------------------------------------------------
mailto:Torsten.Sillke@uni-bielefeld.de
**********************************************************/

struct graph {
   int vertices;
   int edges;
   int *edge_a;
   int *edge_b;

   graph(int v, int e, int *a, int *b)
     : vertices(v), edges(e), edge_a(a), edge_b(b) {};
};


static bool OneBit (unsigned int w)
{
      unsigned wm = w-1;
      return (w ^ wm) >> 1 == wm;
}


ZZ cube_complexity (int dim=3)
{
   int i, j;
   int v = 1<<dim;
   ZZ     det;     //ntl
   mat_ZZ matrix;  //ntl

   matrix.SetDims(v,v);

   for (i=0; i<v; i++) {
     for (j=0; j<v; j++) {
       if ( OneBit(i ^ j) )
         matrix[i][j] = -1;
     }
     matrix[i][i] += dim;  /* matrix D */
   }

   // compute det of mat11.
   for (i=1; i<v; i++) {
     matrix[i][0] = matrix[0][i] = 0;
   }
   matrix[0][0] = 1;

   determinant( det, matrix );
   return det;
}

ZZ complexity (graph &g)
{
   int i, j;
   int v = g.vertices;
   int e = g.edges;
   ZZ     det;     //ntl
   mat_ZZ mat;     //ntl

   mat.SetDims(v,v); // init to the zero matrix

   for (i=0; i<e; i++) {
     mat[g.edge_a[i]][g.edge_b[i]] -= 1;  /* matrix B */
     mat[g.edge_b[i]][g.edge_a[i]] -= 1;  /* matrix B */
     mat[g.edge_a[i]][g.edge_a[i]] += 1;  /* matrix D */
     mat[g.edge_b[i]][g.edge_b[i]] += 1;  /* matrix D */
   }

   // compute det of mat11.
   for (i=1; i<v; i++) {
     mat[i][0] = mat[0][i] = 0;
   }
   mat[0][0] = 1;

   determinant( det, mat );
   return det;
}

ZZ complexity (graph &g, int subgraph)
{
   int bit;
   int i, j;
   int v = g.vertices;
   int e = g.edges;
   int v2= v/2;
   int vertex[32];
   int map[32];
   ZZ  det;        //ntl
   mat_ZZ mat;     //ntl

   mat.SetDims(v2,v2); // init to the zero matrix

   // empty subgraph
   for (i=0; i<v; i++) 
      vertex[i] = 0;

   // select vertices of the subgraph.
   for (bit=0; bit<v2; bit ++) {
      if (subgraph & (1 << bit))
         vertex[v-1-bit] = 1;
      else
         vertex[bit] = 1;
   }

   // construct map
   for (i=j=0; i<v; i++) {
      map[i] = vertex[i] ? j++ : -1;
   }

   for (i=0; i<e; i++) {
     int a = map[g.edge_a[i]];
     int b = map[g.edge_b[i]];
     if (a>=0 && b>=0) {
        mat[a][b] -= 1;  /* matrix B */
        mat[b][a] -= 1;  /* matrix B */
	mat[a][a] += 1;  /* matrix D */
	mat[b][b] += 1;  /* matrix D */
     }
   }
 
   // compute det of mat11.
   for (i=1; i<v2; i++) {
     mat[i][0] = mat[0][i] = 0;
   }
   mat[0][0] = 1;

   determinant( det, mat );

#if 0
   if (det > 0) {
      cout << setw(3) << subgraph << " Subgraph :";
      for (i=0; i<v; i++) {
	 if (vertex[i])
            cout << setw(3) << i;
      }
      cout << " :" << setw(8) << det << endl;
   }

#endif

   return det;
}

int main()
{
   // edges of the cube
   int c_edge_a[12] = { 0, 0, 0, 1, 1, 2, 2, 3, 4, 4, 5, 6 };
   int c_edge_b[12] = { 1, 2, 7, 3, 5, 3, 6, 4, 5, 6, 7, 7 };

   // edges of the octahedron
   int o_edge_a[12] = { 0, 0, 0, 0, 1, 1, 1, 2, 2, 3, 3, 4 };
   int o_edge_b[12] = { 1, 2, 3, 4, 2, 4, 5, 3, 5, 4, 5, 5 };

   // edges of the octahedron, 3 tetrahedra
   int o3edge_a[12] = { 0, 0, 0, 0, 1, 0, 1, 2, 2, 3, 3, 4 };
   int o3edge_b[12] = { 1, 2, 3, 4, 2, 5, 5, 3, 5, 4, 5, 5 };

   // edges of the dodecahedron
   int d_edge_a[30] = { 0, 0, 0, 1, 1, 2, 2, 3, 3, 4,
                        5, 5, 6, 6, 7, 8, 8, 9,10,10,
                       11,12,12,13,14,15,15,16,17,18};

   int d_edge_b[30] = { 1, 2,19, 3, 5, 4,14, 4, 7, 8,
                        6,17, 7,11, 9, 9,13,10,11,12,
                       15,13,16,14,18,16,17,18,19,19};

   // edges of the dual of the rhombic dodecahedrom
   int r_edge_a[24] = { 0, 0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3,
                        4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9,10};

   int r_edge_b[24] = { 1, 3, 4, 5, 2, 5, 7, 3, 6, 7, 4, 6,
                        9,10, 8, 9,10,11, 8,11, 9,11,10,11};

   // edges of the triangular prism
   int p_edge_a[9] = { 0, 0, 0, 1, 1, 2, 3, 3, 4};
   int p_edge_b[9] = { 1, 2, 3, 2, 4, 5, 4, 5, 5};

   graph         cube( 8, 12, c_edge_a, c_edge_b);
   graph octahedron  ( 6, 12, o_edge_a, o_edge_b);
   graph octahedron3 ( 6, 12, o3edge_a, o3edge_b);
   graph dodecahedron(20, 30, d_edge_a, d_edge_b);
   graph dual_rhombic(12, 24, r_edge_a, r_edge_b);
   graph       prism3( 6,  9, p_edge_a, p_edge_b);
   int i;
   ZZ  tot;

   cout.setf(ios::fixed); cout.precision(0);
   cout << "square " << cube_complexity(2) << endl;
   cout << "cube   " << cube_complexity(3) << endl;
   cout << "cube-4 " << cube_complexity(4) << endl;
   cout << "cube             " << complexity(cube) << endl;
   cout << "octahedron       " << complexity(octahedron) << endl;
   cout << "dodecahedron     " << complexity(dodecahedron) << endl;
   cout << "dual rhombicD    " << complexity(dual_rhombic) << endl;
   cout << "triangular prism " << complexity(prism3) << endl;
   cout << "octahedron3      " << complexity(octahedron3) << endl;

   tot = 0;
   for (i=0; i<(1<<3); i++) {
      tot += complexity(cube, i);
   }
   cout << "cube-subgraphs " << tot << endl;

   tot = 0;
   for (i=0; i<(1<<9); i++) {
      tot += complexity(dodecahedron, i);
   }
   cout << "dodecahedron-subgraphs " << tot << endl;

   return 0;
}