#include <iostream.h>
#define NODES 8

// prints all the trees on K_NODES that have edge 12.

bool intree[NODES];
int lstart[NODES-1];
int lend[NODES-1];

void print () {
  for (int i=0;i<NODES-1;i++) {
    cout << (lstart[i]+1);
    cout << (lend[i]+1);
    cout << ";";
  }
  cout << "\n";
}

void recurse (int nodessofar) {
  if (nodessofar == NODES) {
    // we have a solution
    print();
  } else for (int i=0;i<NODES;i++) if (!intree[i]) {
    // add node i to the tree.
    
    // is node i of lower count than the biggest node in
    // the tree (which is lend[nodessofar-2])?

    if (i < lend[nodessofar-2]) {
      // must attach i to that node.
      lstart[nodessofar-1] = i;
      lend[nodessofar-1] = lend[nodessofar-2];
      intree[i] = true;
      recurse(nodessofar+1);
      intree[i] = false;
    } else for (int j=0;j<NODES;j++) if (intree[j]) {
      // i is biggest.  Attach to each node in the tree, in order.
      lstart[nodessofar-1] = j;   
      lend[nodessofar-1] = i;   
      intree[i] = true;
      recurse(nodessofar+1);
      intree[i] = false;
    }
  }
}

int main () {
  for (int i=0;i<NODES;i++) intree[i] = false;

  // put the 12 edge in the tree.
  intree[0] = true;
  intree[1] = true;
  lstart[0] = 0;
  lend[0] = 1;

  recurse(2);
  return(0);
}