#include <cstdio>
#include <cassert>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <list>
#include <unordered_set>
#include <map>
#include <set>
#include <omp.h>
using namespace std;

/* A utility program to display an element from a set of templates,
   together with some additional information on its faces and other
   properties.  */

#include "torus-common.h"

struct noncc_test : public elist_test
{
  surf_graph *g;
  int len;

  noncc_test (surf_graph *_g, int _l)
    {
      g = _g;
      len = _l;
    }

  virtual bool operator() (vector<edge *> &cyc)
    {
      int l = cyc.size ();

      if (l < len)
	return false;

      flfmap inside;
      return g->vs_inside_cycle (cyc, &inside) < 0;
    }
};
static bool
noncontractible_cycle (surf_graph *g, int l)
{
  noncc_test tst (g, l);
  return g->cycles (l, tst);
}

static int
edgewidth (surf_graph *g)
{
  for (int l = 4; ; l++)
    if (noncontractible_cycle (g, l))
      return l;
}

static void
print_stats (surf_graph *g)
{
  int fsl[100];
  int flf[100];
  bool any_inf = false;

  for (int i = 0; i < 100; i++)
    fsl[i] = flf[i] = 0;

  for (int f = 0; f < g->nfs (); f++)
    {
      int len = g->fs[f].length ();
      fsl[len]++;
      flfmap &ff = g->fs[f].floating_faces;
      if (ff.size () > 1)
	abort ();
      for (flfmap::iterator i = ff.begin (); i != ff.end (); ++i)
	{
	  if (i->second > 1)
	    abort ();
	  if (i->first != len)
	    abort ();
	  flf[i->first] += i->second;
	}

      if (len >= 6
	  && !(ff.size () == 1 && ff.begin()->first == len))
	any_inf = true;
    }

  bool con = true;
  for (int v = 0; v < g->nvs (); v++)
    {
      set<int> ifs;

      for (edge_iter_nbr e(g->vs[v]); !e.end_p (); ++e)
	{
	  if (ifs.count ((*e)->left) > 0)
	    con = false;
	  ifs.insert ((*e)->left);
	}
    }

  edge *re = NULL;
  for (int v = 0; v < g->nvs (); v++)
    {
      edge *e = g->redundant_edge_at (v);
      if (e)
	re = e;
    }

  printf ("%d vertices; ", g->nvs ());
  if (any_inf)
    printf ("infinite class; ");
  if (re)
    printf ("reducible edge %d--%d; ", re->opp->to, re->to);
  if (!con)
    printf ("representativity 1; ");
  if (g->is_colorable_wno ())
    printf ("colorable; ");
  for (int i = 0; i < 100; i++)
    if (fsl[i])
      printf ("%d %d-faces; ", fsl[i], i);
  for (int i = 0; i < 100; i++)
    if (flf[i])
      printf ("%d floating %d-faces; ", flf[i], i);
  printf ("edge-width %d\n", edgewidth (g));
/*  if (g->minimize ())
    printf ("not minimal; "); */
  printf ("recodes to");
  vector<int> code;
  g->get_min_code (code);
  for (vector<int>::iterator i = code.begin (); i != code.end (); ++i)
    printf (" %d", *i);

  printf ("\n");
}

int main (int argc, char *argv[2])
{
  vector<int> code;
  int k = 1;
  int n = argc >= 2 ? atoi (argv[1]) : 1;

  while (read_code (stdin, code))
    {
      if (k == n)
	{
	  surf_graph g(code);
	  printf ("graph %d: ", k);
	  print_stats (&g);
	  g.print (stdout);
	  return 0;
	}
      k++;
    }
  return 0;
}