/* Tutorial on Reverse Search */
/* Section 6: Tree generation  R*/

/* input: n (number of edges) */

#include <stdio.h>
#define TRUE 1
#define FALSE 0

typedef int tree[100];  /* nodes from 0..n, tree[i] is parent of i     */

/* global variables */
int n;			/* number of edges in tree */
int depth=0;            /* depth of current node in reverse search tree */

void output (tree v)
/* output parent of node i, i=1..n */
{
  int i;
  for (i = 1; i <= n; i++)
    printf (" %d", v[i]);
  printf ("   depth=%d\n",depth);
}

void next(tree v, int* r, int* s)
/* increment j and possibly i skipping any node whose parent is not root */
{
 int i=(*r), j=(*s);
 j++;
 if ( i == j) j++;
 if (j > n )
    {  i++;
       j=1;
    }
 if( v[i] != 0 ) i=n+1;  /* no need to consider any more edges */
                         /* reverse will always be false       */
 (*r)=i; (*s)=j;
}

void copy (tree w, tree v)
{
  int i;
  for (i = 1; i <= n; i++)
    w[i] = v[i];
}

int equal (tree w, tree v)
{
  int i;
  for (i = 1; i <= n; i++)
    if (w[i] != v[i]) return FALSE;
  return TRUE;
}

int root (tree v)
{
  int i;
  for (i = 1; i <= n; i++)
    if (v[i] != 0) return FALSE;
  return TRUE;
}

int Adj (tree v, int i, int j)          /*   adjacency oracle */
{                                       /* i is child of root */
 int p;
 p=v[j];
 while ( p != 0 && p != i ) p=v[p];
 if (p==i) return FALSE;           /* i is ancestor of j    */
 v[i]=j;                           /* j becomes parent of i */
 return TRUE;                                                     
}

void f (tree v, int* i, int* j)                 /* local search function */
{                        /* set i,j s.t v=Adj(f(v),i,j)  then set v=f(v) */
  int k=1;
  while ( k <= n && v[k] ==  0 ) k++;
  if (k <= n)                                   /* v is not root of tree */
   { (*i)=k; (*j)=v[k];
     v[k]=0;
   }
}

int reverse (tree v, int i, int j)
{
  tree w;
  copy (w, v);
  Adj (w,i,j);
  f (w,&i,&j);     /* i, j get changed, but are not returned to reversearch */
  return equal (v, w);
}


int reversesearch (tree v)
{
  int i=1, j=1, count=1;
  output (v);
  while ( i <= n )
    {
      do next(v,&i,&j);
          while (i <= n && !reverse (v,i,j));
      if (i <= n)
        {
          Adj (v,i,j);
          count++; depth++;
          output(v);
          i=1; j=1;
        }
      else if (!root(v)) 
             {
              f(v,&i,&j);
              depth--;
             }
    }
  return count;
}


int main ()			/*  reverse search for trees  */
{
  tree v;        /* v[i] is parent of i in tree rooted at 0 */
  int i,count;

  scanf ("%d", &n);
  for (i = 1; i <= n; i++) v[i]=0;

  count = reversesearch (v);
  printf ("\nnumber of trees=%d\n", count);
  return 0;
}