import java.io.*;
import java.util.*;

//! -------- KSet code is stablised---------------------------------------------------
//! -----------------------------------------------------------------------------------
//! Ksets begin with index 1

class KSet
	{
	private int leafMax;
	private boolean array[];
	private int leafCount;

	private int id;
	private KSet parent;
	private Vector children;

	public void setID( int idval )
		{
		this.id = idval;
		}

	public int getID()
		{
		return id;
		}

	public void setParent( KSet p )
		{
		this.parent = p;
		}

	public KSet getParent()
		{
		return parent;
		}

	//! Should I check to see if it's unique?
	public void addChild( KSet p )
		{
		children.add(p);
		}

	public int countChildren()
		{
		return children.size();
		}

	public Vector getChildren()
		{
		return children;
		}

	//! We assume that 'avoid' is already in the vector nw
	public void scanChildTree( KSet root, KSet avoid, Vector nw, boolean strictsubset[][] )
		{
		if( this.parent != null )
			{
			if( this != avoid )
				{
				if( !strictsubset[avoid.getID()][this.getID()] )
					{
					if( this.parent == root ) nw.add(this);
					else
					if( strictsubset[avoid.getID()][this.parent.getID()] ) nw.add(this); 
					}
				}
			}

		//! Ok, now scan all the kids.

		Enumeration e = children.elements();
		while( e.hasMoreElements() )
			{
			KSet kind = (KSet) e.nextElement();

			kind.scanChildTree( root, avoid, nw, strictsubset );
			}

		}

	public KSet( int leaves )
		{
		this.leafMax = leaves;
		array = new boolean[ leafMax ];
		children = new Vector();
		}

	public void addLeaf( int l )
		{
		if( array[l-1] == false ) leafCount++;
		array[l-1] = true;
		}

	public void removeLeaf( int l )
		{
		if( array[l-1] == true ) leafCount--;
		array[l-1] = false;
		}

	public boolean containsLeaf( int l )
		{
		if( l > leafMax ) return false;
		return array[l-1];
		}

	//! Returns true if this is a subset of 'two'

	public boolean isSubsetOf( KSet two )
		{
		if( this.leafCount > two.leafCount ) return false;
		
		for( int x=0; x<array.length; x++ )
			{
			if( (array[x] == true) && (two.array[x] == false) ) return false;
			}
		return true;
		}

	public int size()
		{
		return leafCount;
		}

	public boolean empty()
		{
		return( leafCount==0 );
		}

	public int getFirstElement()
		{
		for( int x=0; x<array.length; x++ )
			{
			if( array[x] == true ) return (x+1);
			}

		System.out.println("ERROR#1: Set was empty!");
		return -1;
		}


	public void dump()
		{
		if( Marlon.DEBUG )
			{
			System.out.print("[");
			for(int x=0; x<leafMax; x++ )
				{
				if(array[x] == true) System.out.print((x+1)+" ");
				}
			System.out.println("]");
			}
		}

	public boolean sameAs( KSet second )
		{
		int smaller, bigger;
		boolean longer[] = null;
	
		if( this.leafCount != second.leafCount ) return false;

		if( leafMax < second.leafMax )
			{
			smaller = leafMax;
			bigger = second.leafMax;
			longer = second.array;
			}
		else
			{
			smaller = second.leafMax;
			bigger = leafMax;
			longer = this.array;
			}

		for( int x=0; x<smaller; x++ )
			{
			if( array[x] != second.array[x] ) return false;
			}

		for( int x=smaller; x<bigger; x++ )
			{
			if( longer[x] ) return false;
			}

		return true;
		}


	public int getMaxSize()
		{
		return leafMax;
		}


	}


//! --------------------------------------------------------
//! This part of the code is now ready.

class Graph
{
private int leaves;

public static int NOT_VISITED = 0;
public static int LEFT = 1;
public static int RIGHT = 2;

boolean adj[][];
int deg[];

public Graph(int n)
	{
	leaves = n;
	adj = new boolean[n][n];
	deg = new int[n];
	}

public boolean containsEdge(int a, int b)
	{
	return( adj[a-1][b-1] );
	}

public void addEdge(int a, int b)
	{
	if( adj[a-1][b-1] == false )
		{
		deg[a-1]++;
		deg[b-1]++;
		}		

	//! These things are always added in unison...
	adj[a-1][b-1] = adj[b-1][a-1] = true;
	}

public int degree(int a)
	{
	return deg[a-1];
	}

//! Inspects if the vertices form two disjoint cliques and, zo ja,
//! returns the partition (LEFT/RIGHT) in the return array
//! otherwise returns null
//! The array should be indexed on [1...leaves]

public int[] getDoubleClique()
	{
	//! I should first check if the complement graph is bipartite.
	//! If there are more then 2 components, then it won't be
	//! And then I can check if it is a complete bipartite graph.
	//! That is: everyone on LEFT has degree equal to RIGHT, and
	//! viceversa

	int visited[] = new int[leaves+1];

	visited[0] = -1000;

	//! We'll start with vertex 1
	int start = 1;

	boolean success = visit( 1, LEFT, visited );

	if( !success ) return null;

	int lClique = 0;
	int rClique = 0;

	for(int scan=1;scan<=leaves; scan++ )
		{
		if( visited[scan] == NOT_VISITED ) return null;
		if( visited[scan] == LEFT ) lClique++;
		if( visited[scan] == RIGHT ) rClique++;
		}

	//! So if we've got here we know how many guys are in the
	//! left clique, and in he right...

	for( int scan=1; scan<=leaves; scan++ )
		{
		if( visited[scan] == LEFT )
				{
				if( degree(scan) != (lClique-1) ) return null;
				}
		else
				{
				if( degree(scan) != (rClique-1) ) return null;
				}

		}

	return visited;
	}


private boolean visit( int vertex, int colourWith, int state[] )
	{
	if( state[vertex] != NOT_VISITED )
		{
		if( state[vertex] != colourWith ) return false;
		return true;
		}

	state[vertex] = colourWith;

	int childCol;
	if( colourWith == LEFT ) childCol = RIGHT;
		else childCol = LEFT;

	//! Now, try all COMPLEMENT children...

	for( int scan=1; scan<=leaves; scan++ )
		{
		if( vertex==scan ) continue;
		if( !containsEdge( vertex, scan ) )
			{
			boolean gelukt = visit( scan, childCol, state );
			if( !gelukt ) return false;
			}

		}

	return true;
	}


}


//! convention: ab|c where a<b
//! Assumes that leaves are numbered 1...n
//! !!!Assumes that there are no missing leaves!!!

class TripletSet
	{
	private Vector tripVec;
	private int numLeaves;
	private boolean finalised;
	private boolean lookup[][][];

	public TripletSet()
		{
		tripVec = new Vector();
		numLeaves = 0;
		finalised = false;
		}

	public Enumeration elements()
		{
		return tripVec.elements();
		}

	//! Nasty....don't use except in dire circumstances
	public int tellLeaves()
		{
		return numLeaves;
		}

	//! Checks to see if all leaves on 1...n are used where n = numLeaves
	//! This is currently very slow...

	public boolean isClosed(int errorTip[])
		{
		boolean seen[] = new boolean[ numLeaves+1 ];
		Enumeration e = tripVec.elements();
		while( e.hasMoreElements() )
			{
			int t[] = (int []) e.nextElement();
			seen[ t[0] ] = true;
			seen[ t[1] ] = true;
			seen[ t[2] ] = true;
			}
		for( int scan=1; scan<seen.length; scan++ )
			{
			if( !seen[scan] )
				{
				errorTip[0] = scan;
				return false;
				}
			}
		return true;
		}

	//! This is currently very slooow.
	public boolean isDense(int errorTrip[])
		{
		for( int x=1; x<=numLeaves; x++ )
		for( int y=1; y<=numLeaves; y++ )
		for( int z=1; z<=numLeaves; z++ )
			{
			if( (x==y) || (x==z) || (z==y) ) continue;
			if( !containsTriplet(x,y,z) && !containsTriplet(x,z,y) && !containsTriplet(z,y,x) )
				{
				errorTrip[0] = x;
				errorTrip[1] = y;
				errorTrip[2] = z;
				return false;
				}
			}
		return true;
		}


	public void addTriplet(int a, int b, int c)
		{
		if( finalised == true )
			{
			System.out.println("ERROR#2: Major error: tried adding triplet to finalised triplet set.");
			System.exit(0);
			}

		int swap = 0;

		//! swap a and b around, if necessary...

		if( a>b )
			{
			swap = a;
			a = b;
			b = swap;
			}

		if( this.containsTriplet(a, b, c) ) return;

		//! What is the highest leaf seen so far?

		int highest = 0;

		if( (a>b) && (a>c) ) highest = a;
		else
		if( (b>a) && (b>c) ) highest = b;
		else
		highest = c;

		if( highest > numLeaves )
			{
			numLeaves = highest;
			}


		int myTriplet[] = new int[3];
		myTriplet[0] = a;
		myTriplet[1] = b;
		myTriplet[2] = c;

		tripVec.add( (int []) myTriplet );				
		}

	public int countTriplets()
		{
		return tripVec.size();
		}


	public boolean containsTriplet(int a, int b, int c)
		{
		int swap = 0;

		if( finalised == true )
			{
			return ( lookup[a][b][c] || lookup[b][a][c] );
			}

		//! swap a and b around, if necessary...

		if( a>b )
			{
			swap = a;
			a = b;
			b = swap;
			}

		Enumeration e = tripVec.elements();
		while( e.hasMoreElements() )
			{
			int triplet[] = (int []) e.nextElement();
			if( (triplet[0] == a) && (triplet[1] == b) && (triplet[2] == c) ) return true;
			}

		return false;
		}


	public void dumpTriplets()
		{
		System.out.println(tripVec.size()+" elements on "+numLeaves+" leaves.");

		Enumeration e = tripVec.elements();
		while( e.hasMoreElements() )
			{
			int triplet[] = (int []) e.nextElement();
			System.out.println(triplet[0]+","+triplet[1]+"|"+triplet[2]);
			}
		}

	//! After calling this, look-up is miles faster, BUT you can't change the set anymore!!!

	public void finaliseAndOptimise()
		{
		finalised = true;

		lookup = new boolean[numLeaves+1][numLeaves+1][numLeaves+1];

		Enumeration e = this.tripVec.elements();

                while( e.hasMoreElements() )
                        {        
                        int t[] = (int []) e.nextElement();
                                
			int x = t[0];
			int y = t[1];
			int z = t[2];

			lookup[x][y][z] = true;
			lookup[y][x][z] = true;
                        }

		} 


	//! Not sure whether this is a correct implementation, try and verify the
	//! correctness of this...I think it should be approximately cubic time...
	//! Ah I now understand why this works. At any one iteration, X cup Z is
	//! the current SN set, and X cup Z contains all leaves which were
	//! added because of triplets of the form x1 * | x2

	public KSet FastComputeSN( int x, int y )
		{
		int n = numLeaves;

		KSet X = new KSet(n);
		KSet Z = new KSet(n);

		X.addLeaf(x);
		Z.addLeaf(y);

		while( Z.empty() == false )
			{
			int z = Z.getFirstElement();

			for( int a=1; a<=n; a++ )
				{
				if( X.containsLeaf(a) == false ) continue;

				for( int c=1; c<=n; c++ )
					{
					if( X.containsLeaf(c) || Z.containsLeaf(c) ) continue;

					if( this.containsTriplet(a, c, z) || this.containsTriplet(z, c, a) )
						{
						Z.addLeaf(c);

						//! I think their algorithm mistakenly implies that we can 'break' here
						}

					}				
				X.addLeaf(z);
				Z.removeLeaf(z);
				}

			}	
		return X;
		}

	public biDAG buildMarlon()
		{
		Marlon.report("Constructing SN-sets.");

		Vector sn = this.getSNSets();

		//! Ok, so now we have a vector containing all SN-sets.
		//! We need to build an intelligent data-structure out of them, to make
		//! everything nice and fast.

		Marlon.report("Ranking the SN-sets in terms of size.");

		//! snrank begins at [1], goes up until [this.numLeaves]

		Vector snrank[] = new Vector [ this.numLeaves+1 ];
		for( int x=1; x<snrank.length; x++ )
			{
			snrank[x] = new Vector();
			}

		//! This makes a ranking based on the number of leaves...
		for( int x=0; x<sn.size(); x++ )
			{
			KSet k = (KSet) sn.elementAt(x);
			int l = k.size();
			snrank[l].add( k );
			}		

		Marlon.report("Finishing ranking, now putting in linear order...");

		//! ---------------------------------------------
		//! This creates an SN-set array which has
		//! elements of increasing size...

		KSet ordered[] = new KSet[ sn.size() ];

		int at = 0;
		for( int x=1; x<snrank.length; x++ )
			{
			Enumeration e = snrank[x].elements();
			while( e.hasMoreElements() )
				{
				ordered[at++] = (KSet) e.nextElement();
				}
			}

		//! Hopefully this is correct...
		KSet trivial = ordered[ordered.length-1];

		//! -----------------------------------------------

		Marlon.report("Constructing SN-tree: first the parent relationship");

		//! This should build a correct parent relationship.

		boolean strictsubset[][] = new boolean[sn.size()][sn.size()];
		//! NOTE: strictsubset is FALSE for [i][i]

		for( int x=0; x<sn.size(); x++ )
			for( int y=0; y<sn.size(); y++ )
				{
				if( x == y ) continue;
	
				KSet s = (KSet) sn.elementAt(x);
				KSet t = (KSet) sn.elementAt(y);

				if( s.isSubsetOf(t) )
					{
					strictsubset[s.getID()][t.getID()] = true;

					KSet p = s.getParent();
					if( p == null )
						{
						s.setParent(t);

						/*
						s.dump();
						Marlon.report("is a subset of ");
						t.dump();
						*/

						}
					else
						{
						//! In this way we will ultimately choose
						//! the smallest superset of s, as its parent...
						if( t.size() < p.size() )
							{
							s.setParent(t);

							/*
							s.dump();
							Marlon.report("is a subset of ");
							t.dump();
							*/

							}
						}					

					}
							
				}


		//! -----------------------------------------------
		//! Now we can build the child relationship...

		Marlon.report("Building the SN child relationship...");

		for( int x=0; x< sn.size(); x++ )
			{
			KSet k = (KSet) sn.elementAt(x);

			KSet p = k.getParent();

			if( p == null ) continue;
	
			p.addChild( k );
			}

		//! ---------------------------------------------------

		Marlon.report("Starting dynamic programming phase.");

		int numsn = sn.size();

		//! ----------------------------------------------------
		//! This will hold the solution value...

		int optarr[] = new int[numsn];
		biDAG opnet[] = new biDAG[numsn];

		for( int y=0; y<numsn; y++ )
			{
			optarr[y] = -1;		//! Means: not yet considered / did not work...
			}

		//! Cycle through the subsets, from small to large...
		for( int x=0; x<ordered.length; x++ )
			{		
			KSet s = ordered[x];

			Marlon.report("Outer loop, index="+s.getID()+", S=");
			s.dump();


			//! stores the intermediate results...
			//! Confusingly, we use very last value as the g(S, \empty) value...
			//! hence numsn+1

			int table[] = new int[numsn+1];
			biDAG tableNetwork[] = new biDAG[numsn+1];

			for( int fill=0; fill<table.length; fill++ ) table[fill] = -1;

			//! Bear in mind that s might be the trivial triplet set!!!

			int splnum[] = new int[1];

			if( s.countChildren() != 2 )
			sploop: for( int y=0; y<x; y++ )
				{
				KSet sprime = ordered[y];

				Marlon.report("Inner loop: S'=");
				sprime.dump();

				if( !strictsubset[sprime.getID()][s.getID()] ) continue;

				//! Ok, sprime is a subset of s, so we are ready to build
				//! a new set of SN-sets...

				Marlon.report("S' is a subset of S, so going further...");

				Vector nw = new Vector();

				nw.add( sprime );

				//! We're going to add SN-sets which are subsets of S which
				//! are maximal assuming they do not contain S'
				//! Idea: search through the child subtree of S', 
				//! if the parent is equal to S *OR* the parent
				//! contains S', then it goes in...

				s.scanChildTree( s, sprime, nw, strictsubset );

				Marlon.report("Got the S'-induced SN-sets...");

				if( nw.size() == 2 ) continue sploop;

				if(Marlon.DEBUG)
					{
					Enumeration e = nw.elements();
					while( e.hasMoreElements() )
						{
						((KSet)e.nextElement()).dump();
						}
					}

				KSet revMap[] = new KSet [nw.size()+1];
			
				TripletSet tnew = partialBuildTPrime( nw, revMap, sprime, splnum );


			
				Marlon.report("Built the meta triplet set.");
				Marlon.report("Contains "+tnew.countTriplets()+" triplets.");

				//! revMap[i] (index starts at 1) points to the KSet
				//! that is represented in the biDAG by leaf i...

				biDAG bd = tnew.buildSimpleLevel1(splnum[0]);

				//! Couldn't build a simple level-1 network with it...
				//! you will also get null back if only 2 sn-sets in nw
				//! I think that's OK

				if( bd == null )
					{
					Marlon.report("Couldn't build simple level-1 network.");
					continue sploop;
					}

				//! Puts a link in each leaf to its corresponding SN-set
				bd.buildSNCorrespondence(revMap);

				//! Ok, could build a simple level-1, so add the reticulation
				//! nodes up...

				int total = 1;

				for( int p=0; p<nw.size(); p++ )
					{
					KSet brick = (KSet) nw.elementAt(p);
					int brickID = brick.getID();

					//! If one of the SN-sets can't be done, we have to skip...
					if( optarr[brickID] == -1 ) continue sploop;
					
					total = total + optarr[ brickID ];
					}

				//! this sets the value of g(s,sprime)
				table[ sprime.getID() ] = total;
				tableNetwork[ sprime.getID() ] = bd;
				}

			//! Now all the g(S, .) values have been computed, except the case (S,\empty)

			if( s.countChildren() == 2 )
				{
				Marlon.report("Also trying no-gall option...");
				Vector v = s.getChildren();
				KSet k1 = (KSet) v.elementAt(0);
				KSet k2 = (KSet) v.elementAt(1);
	
				if( (optarr[k1.getID()] != -1) && (optarr[k2.getID()] != -1) )
					{
					table[ table.length-1 ] = optarr[ k1.getID() ] + optarr[ k2.getID() ];	

					biDAG c = biDAG.cherry12();
				
	                                c.child1.snset = k1;
	                                c.child2.snset = k2;

					tableNetwork[ tableNetwork.length-1 ] = c;
					}
				}

			//! Now, we are ready to compute the minimum...

			int min = this.numLeaves+10;	//! Just a big number...
			int minIndex = -1000;
			boolean feasible = false;

			Marlon.report("Scanning for minimum...");

			for( int scan=0; scan<table.length; scan++ )
				{
				if( table[scan] != -1 )
					{
					feasible = true;
					if( table[scan] < min )
						{
						min = table[scan];
						minIndex = scan;
						}

					}

				}

			if( !feasible )
				{
				if( s.size() == 1 )
					{
					optarr[s.getID()] = 0;
					opnet[s.getID()] = null;	//! I think this is ok...
					}

				else	{
					return null;
					}
				}

			if( feasible )
				{
				Marlon.report("Found the minimum for this S, that's "+min);
				Marlon.report("Minimum index is "+minIndex);				
				optarr[s.getID()] = min;
				opnet[s.getID()] = tableNetwork[minIndex];
				}
			}

		if( optarr[trivial.getID()] == -1 ) return null;

		//! Finally, build the network...

		biDAG root = opnet[trivial.getID()];

		root.assembleNetwork( opnet );

		root.resetVisited();

		return root;
		}

	//! Eliminates duplicates...			
	//! Returns also the trivial set I think...
	//! Gives every SN-set a unique index, starting at 0

	private Vector getSNSets()
		{
		Vector temp = new Vector();

		int n = numLeaves;

		//! Build all singleton SN-sets i.e. of the form SN(x)
		//! These are obviously all disjoint...

		int index = 0;

		for( int x=1; x<=n; x++ )
			{
			KSet K = new KSet(n);

			//! SNSet indices begin at 0!
			K.setID( index++ );

			K.addLeaf(x);

			temp.add( (KSet) K);

			if(Marlon.DEBUG)
				{
				System.out.println("SN set "+(index-1));
				K.dump();
				}
			}

		//! Build all sets of the form SN(x,y)
		//! 		

		for( int x=1; x<=n; x++ )
			{
			for( int y=(x+1); y<=n; y++ )
				{
				KSet K = FastComputeSN(x,y);

				boolean alreadyIn = false;

				for( int scan=0; scan<temp.size(); scan++ )
					{
					KSet comp = (KSet) temp.elementAt(scan);
					if( K.sameAs(comp) )
						{
						alreadyIn = true;
						break;
						}
					} 

				if( !alreadyIn )	
						{
						K.setID( index++ );
						temp.add( (KSet) K );

						if(Marlon.DEBUG)
							{
							System.out.println("SN set "+(index-1));
							K.dump();
							}

						}
				}
			}			

		return temp;
		}

	//! This is a bit different to buildTPrime because
	//! the SN-sets in sn only partition a subset of the leaves...
	//! splnum[0] sends back the leaf number of the leaf corresponding to sprime

	public TripletSet partialBuildTPrime( Vector sn, KSet revMap[], KSet sprime, int splnum[] )
		{
		if( sn.size() == 2 ) return null;

		int metaLeaves = sn.size();

		int snmap[] = new int[ this.numLeaves+1 ];
		//! because leaves always begin at 1...

		int ml = 1;
		Enumeration e = sn.elements();
		while( e.hasMoreElements() )
			{
			KSet k = (KSet) e.nextElement();

			//! Shows that leaf ml points to SNSet k;
			revMap[ml] = k;

			if( k == sprime ) splnum[0] = ml;

			for( int x=1; x<=this.numLeaves; x++ )
				{
				if( k.containsLeaf(x) ) snmap[x] = ml;
				}
			ml++;	//! increment the meta-leaf...
			}

		TripletSet tnew = new TripletSet();

                Enumeration f = tripVec.elements();
		while( f.hasMoreElements() )
			{
                        int t[] = (int []) f.nextElement();

			//! If any of the leaves fall out of the range, don't include the triplet...
			if( (snmap[t[0]] == 0) || (snmap[t[1]] == 0) || (snmap[t[2]] == 0) ) continue;

                        int a = snmap[t[0]];
                        int b = snmap[t[1]];
                        if( b == a ) continue;

                        int c = snmap[t[2]];
                        if( (c==a) || (c==b) ) continue;

                        tnew.addTriplet( snmap[t[0]], snmap[t[1]], snmap[t[2]] );
			}
		return tnew;
		}


	private Graph buildAhoGraph()
		{
		//! Cycle through all triplets...

		Graph aho = new Graph( numLeaves );

		Enumeration e = tripVec.elements();
		while( e.hasMoreElements() )
			{
			int t[] = (int []) e.nextElement();

			aho.addEdge( t[0], t[1] );
			}		

		return aho;
		}


	//! private constructor
	//! builds a new TripletSet equal to the current tripletset, with the
	//! difference that all triplets containing leaf s are suppressed;
	//! can be optimised, if needed.

	//! All leaves with an index bigger than s drop their index by 1!!!

	private TripletSet( TripletSet ts, int s )
		{
		tripVec = new Vector();
                numLeaves = 0;

		Enumeration e = ts.tripVec.elements();
		while( e.hasMoreElements() )
			{
			int v[] = (int []) e.nextElement();

			//! If it contains s, throw it away...
			if( (v[0] == s) || (v[1] == s) || (v[2]==s)) continue;
	
			//! Otherwise, put the triple back in (with, where
			//! necessary, adjusted indexing

			int ap = v[0] < s ? v[0] : v[0]-1;
			int bp = v[1] < s ? v[1] : v[1]-1;
			int cp = v[2] < s ? v[2] : v[2]-1;

			addTriplet(ap,bp,cp);
			}			

		}


	//! If you have a vector of leaf nodes, makes space for the
	//! re-insertion of leaf 'correction'

	private void correctLeafNodes( Vector nodes, int correction )
		{
		Enumeration e = nodes.elements();
		while( e.hasMoreElements() )
			{
			biDAG b = (biDAG) e.nextElement();
			if( b.data < correction ) continue;
			b.data++;
			}

		}

	public biDAG buildSimpleLevel1(int recomb)
		{
		if( numLeaves <= 2 )
			{
			Marlon.report("Tried to build simple level-1 with only two leaves.");
			return null;
			}

		//! Skew network...

		Marlon.report("Trying to build a skew simple level-1 network.");

		for( int l=recomb; l<=recomb; l++ )
			{
			//! System.out.println("Suppressing leaf "+l);
			TripletSet ts = new TripletSet( this, l );

			//! So now we have a triplet set where leaf l was suppressed.
			//! We'll have to do all that relabelling rubbish, *zucht*

			biDAG cat = null;

			if( ts.countTriplets() != 0 )
				{
				cat = ts.buildTree();
				}
			else
				{
				//! This can only happen if numLeaves == 3

				cat = biDAG.cherry12();
				}

			if( cat == null ) continue;

			Vector leafOrder = new Vector();

			if( cat.testCaterpillar(leafOrder) != false )
				{
				//! We now actually have enough information to test if this
				//! works...the leaf nodes are in leafOrder. Let's fix the
				//! leaves first...

				correctLeafNodes( leafOrder, l );				

				//! Now there is space for leaf l to be added back in...
				//! There are two possibilities, depending on which of the two
				//! last leaves in the caterpillar we subdivide...

				int catLeaves = leafOrder.size();

				int lookup[] = new int[catLeaves];
				int dfr[] = new int[numLeaves+1];

				for( int scan=0; scan<catLeaves; scan++ )
					{
					lookup[scan] = ((biDAG) leafOrder.elementAt(scan)).data;
					//! System.out.println("lookup["+scan+"] = "+lookup[scan]);
					dfr[lookup[scan]] = scan;
					//! System.out.println("dfr["+lookup[scan]+"] = "+scan);
					}
					
				//! So dfr is kind of the distance from the root, used for fast triplet check

				//! There are two things to try, depending on which bottom edge we subdivide

				//! Let's check the triplets.

				boolean success = true;

				for( int s=0; s<tripVec.size(); s++ )
					{
					int t[] = (int []) tripVec.elementAt(s);

					int x = t[0];
					int y = t[1];
					int z = t[2];

					if( z == l ) continue;		//! is always in
					if( (x == l) && (dfr[z] < dfr[y]) ) continue;
					if( (y == l) && (dfr[z] < dfr[x]) ) continue;

					if( (dfr[z] < dfr[y]) && (dfr[z] < dfr[x]) ) continue;
					success = false;
					break;	
					}


				if( success )
					{
					//! Build the thing and then finish
					Marlon.report("Built a simple skew level-1 network (version 1).");

					Marlon.report("Got here.");

					biDAG newnode = ((biDAG)leafOrder.elementAt(catLeaves-1)).insertAbove(0);

					biDAG newroot = new biDAG();
					newroot.child1 = cat;
					newroot.child2 = newnode;
					newnode.secondParent = newroot;

					biDAG newleaf = new biDAG();
					newleaf.parent = newnode;
					newleaf.data = l;
					newnode.child1 = newleaf;

					return newroot;
					}

				success = true;

				//! Try swapping the last two elements round, and repeat
				int lastA = lookup[catLeaves-1];
				int lastB = lookup[catLeaves-2];
				int swap = dfr[lastA];
				dfr[lastA] = dfr[lastB];
				dfr[lastB] = swap;

				for( int s=0; s<tripVec.size(); s++ )
					{
					int t[] = (int []) tripVec.elementAt(s);

					int x = t[0];
					int y = t[1];
					int z = t[2];

					if( z == l ) continue;		//! is always in
					if( (x == l) && (dfr[z] < dfr[y]) ) continue;
					if( (y == l) && (dfr[z] < dfr[x]) ) continue;

					if( (dfr[z] < dfr[y]) && (dfr[z] < dfr[x]) ) continue;
					success = false;
					break;	
					}

				if( success )
					{
					//! Build the thing and then finish
					Marlon.report("Built a simple skew level-1 network (version 2).");


					 biDAG newnode = ((biDAG)leafOrder.elementAt(catLeaves-2)).insertAbove(0);

                                        biDAG newroot = new biDAG();
                                        newroot.child1 = cat;
                                        newroot.child2 = newnode;
                                        newnode.secondParent = newroot;
                                         
                                        biDAG newleaf = new biDAG();
                                        newleaf.parent = newnode;
                                        newleaf.data = l;
                                        newnode.child1 = newleaf;
                 
                                        return newroot;

					}


				}	//! end if-caterpillar...

			}	//! end leaf suppression loop
		
		//! Non-skew network. Is a bit more complicated..............................

		Marlon.report("Was not skew level-1.");

		Marlon.report("Trying non-skew network level-1.");

		for( int l=recomb; l<=recomb; l++ )
			{
			//! System.out.println("Suppressing leaf "+l);
			TripletSet ts = new TripletSet( this, l );

			//! So now we have a triplet set where leaf l was suppressed.
			//! We'll have to do all that relabelling stuff, *zucht*

			biDAG splits = null;

			if( ts.countTriplets() != 0 )
				{
				splits = ts.buildTree();
				}
			else
				{
				//! This can only happen if numLeaves == 3 I think

				splits = biDAG.cherry12();
				}

			if( splits == null ) continue;

			//! We need splits to have a weird shape...if it doesn't have
			//! that shape it can't be good...it's that old classic again...
			//! I think there are (at most) 4 possibilities here...we can
			//! assume that there is at least one leaf on both sides of the
			//! root

			Vector left = new Vector();
			Vector right = new Vector();

			boolean isSplit = splits.testSplit( left, right );

			if( !isSplit ) continue;

			//! Makes space for leaf l to be added back
			splits.oneLeafAdjustTree(l);

			//! So...let's do this...there could be up to four glueings...
			
			//! try all additions possible...grrrr...this is extremely annoying...

			int leftLookUp[] = new int[ left.size() ];
			int rightLookUp[] = new int[ right.size() ];

			//! This because the leaves may be divided across different sides...

			int leftDfr[] = new int[ numLeaves + 1 ];
			int rightDfr[] = new int[ numLeaves + 1 ];

			int leftTry = 1;
			if( left.size() > 1 ) leftTry = 2;

			int rightTry = 1;
			if( right.size() > 1 ) rightTry = 2;

			for( int lscan = 1; lscan <= leftTry; lscan++ )
				for( int rscan = 1; rscan <= rightTry; rscan++ )
					{
					int leafSide[] = new int[this.numLeaves+1];

					biDAG leftGraft, rightGraft = null;

					for( int x=0; x<left.size(); x++ )
						{
						leftLookUp[x] = ((biDAG) left.elementAt(x)).data;
						leftDfr[leftLookUp[x]] = x;
						leafSide[ leftLookUp[x] ] = Graph.LEFT;
						}
					leftGraft = ((biDAG) left.elementAt( left.size() - 1 ));

					if( lscan == 2 )
						{
						//! swap the order of the last two leaves on the left side

						int last = leftLookUp[ leftLookUp.length - 1 ];
						int penum = leftLookUp[ leftLookUp.length - 2 ];

						int posLast = leftDfr[last];
						int posPenum = leftDfr[penum];

						leftDfr[last] = posPenum;
						leftDfr[penum] = posLast;
						leftGraft = ((biDAG) left.elementAt( left.size() - 2 ));
						}

					for( int x=0; x<right.size(); x++ )
						{
						rightLookUp[x] = ((biDAG) right.elementAt(x)).data;
						rightDfr[rightLookUp[x]] = x;
						leafSide[ rightLookUp[x] ] = Graph.RIGHT;
						}

					rightGraft = ((biDAG) right.elementAt( right.size() -1 ));

					if( rscan == 2 )
						{
						//! swap the order of the last two leaves on the left side

						int last = rightLookUp[ rightLookUp.length - 1 ];
						int penum = rightLookUp[ rightLookUp.length - 2 ];

						int posLast = rightDfr[last];
						int posPenum = rightDfr[penum];

						rightDfr[last] = posPenum;
						rightDfr[penum] = posLast;

						rightGraft = ((biDAG) right.elementAt( right.size() - 2 ));
						}
				
					//! Now we're ready to rock...

					boolean success = true;

					for( int s=0; s<tripVec.size(); s++ )
						{
						int t[] = (int []) tripVec.elementAt(s);

						int x = t[0];
						int y = t[1];
						int z = t[2];

						//! Case z == l

						if( (z == l) && (leafSide[x] != leafSide[y]) )
							{
							success = false;
							break;
							}

						//! Case x == l

						if( (x==l) && (leafSide[y] == leafSide[z]) )
							{
							if( leafSide[y] == Graph.LEFT )
								{
								if( leftDfr[z] > leftDfr[y] )
									{
									success = false;
									break;
									}	
								}
							else if( leafSide[y] == Graph.RIGHT )
								{
								if( rightDfr[z] > rightDfr[y] )
									{
									success = false;
									break;
									}
								}
							
							else System.out.println("Error!");
							}
						

						if( (y==l) && (leafSide[x] == leafSide[z]) )
							{
							if( leafSide[x] == Graph.LEFT )
								{
								if( leftDfr[z] > leftDfr[x] )
									{
									success = false;
									break;
									}	
								}
							else if( leafSide[x] == Graph.RIGHT )
								{
								if( rightDfr[z] > rightDfr[x] )
									{
									success = false;
									break;
									}
								}
							else System.out.println("Error!");
							}						


						}	//! triplet loop

					if( success )
						{
						//! Nou, dit wordt spannend....

						biDAG.glueLeafBetween( leftGraft, rightGraft,l );
						return splits;				
						}


					}	//! lscan/rscan


			}	//! leafSuppression loop...

		Marlon.report("Was not non-skew level-1.");

		return null;
		}


	

	public biDAG buildTree()
		{
		biDAG papa = new biDAG();

		//! Build the Aho graph...
		Graph g = buildAhoGraph();

		//! Split into two cliques...

		int partition[] = g.getDoubleClique();
		
		if( partition == null ) return null;

		/*
		if(Marlon.DEBUG)
			{
			System.out.println("Had the double-clique structure:");
			for(int k=1; k<partition.length; k++ )
				{
				System.out.print(partition[k]+" ");
				}
			System.out.println();
			}
		*/

		//! The partition will have only values LEFT and RIGHT...

		//! At some point we have to stop the recursion. We finish once
		//! one of the two cliques has size <= 2;

		int lCount = 0;
		int rCount = 0;

		//! The 0 element of these guys will not be used...
		int leftList[] = new int[partition.length];
		int rightList[] = new int[partition.length];

		//! The 0 element of these guys will not be used...
		int leftBackMap[] = new int[partition.length];
		int rightBackMap[] = new int[partition.length];

		//! Note here that we begin at 1
		for( int scan=1; scan<partition.length; scan++ )
			{
			if( partition[scan] == Graph.LEFT )
				{
				lCount++;

				leftList[lCount] = scan;

				//! This is the new leaf numbering of leaf scan...

				leftBackMap[scan] = lCount;
				}
			else
			if( partition[scan] == Graph.RIGHT )
				{
				rCount++;
				rightList[rCount] = scan;
				rightBackMap[scan] = rCount;
				}
			else
			System.out.println("ERROR#23");
			} 

		//! -------------------------

		biDAG leftChild = null;
		biDAG rightChild = null;

		//! Here it gets messy...

		if( lCount==1 )
			{
			//! In this case it's just a simple leaf...

			leftChild = new biDAG();

			leftChild.data = leftList[1];
		
			/*
			if(Marlon.DEBUG)
				{
				System.out.println("Setting only data as "+leftList[1]);
				}
			*/

			}
		else
		if( lCount==2 )
			{
			leftChild = new biDAG();
		
			//! Here it's a cherry...
			biDAG gchild1 = new biDAG();
			biDAG gchild2 = new biDAG();

			leftChild.child1 = gchild1;
			leftChild.child2 = gchild2;

			gchild1.data = leftList[1];
			gchild2.data = leftList[2];

			/*
			if(Marlon.DEBUG)
				{
				System.out.println("Setting gchild1 as "+leftList[1]);
				System.out.println("Setting gchild2 as "+leftList[2]);
				}
			*/

			gchild1.parent = leftChild;
			gchild2.parent = leftChild;
			
			}
		else
			{
			/*
			if( Marlon.DEBUG )
				{
				System.out.println("Recursing left...");
				}
			*/

			//! and here we recurse...
			//! get all the triplets in the LEFT partition...
			//! and continue...

			TripletSet leftBranch = new TripletSet();

			Enumeration e = tripVec.elements();
			while( e.hasMoreElements() )
				{
				int v[] = (int []) e.nextElement();

				//! We want all 3 of its elements to be in the left
				//! partition...so for each element check whether it

				if( (partition[v[0]] == Graph.RIGHT) || (partition[v[1]] == Graph.RIGHT) || (partition[v[2]] == Graph.RIGHT) )
					continue;

				//! the backscan variable ensures that the indices are correct...i.e. in
				//! the range [1...leftCount]

				leftBranch.addTriplet( leftBackMap[v[0]], leftBackMap[v[1]], leftBackMap[v[2]] );
				}

			leftChild = leftBranch.buildTree();

			if( leftChild == null ) return null;
		
			/*
			if( Marlon.DEBUG ) System.out.println("Past left recursion");
			*/

			//! Fix labelling in the tree...very crude but zucht let's get it working first...
			leftChild.treeFixLeaves( leftList );
			}		

		//! and now the right branch...

		if( rCount==1 )
			{
			//! In this case it's just a simple leaf...

			rightChild = new biDAG();
			rightChild.data = rightList[1];

			/*
			if(Marlon.DEBUG)
				{
				System.out.println("Setting only data as"+rightList[1]);
				}
			*/

			}
		else
		if( rCount==2 )
			{
			rightChild = new biDAG();
		
			//! Here it's a cherry...
			biDAG gchild1 = new biDAG();
			biDAG gchild2 = new biDAG();

			rightChild.child1 = gchild1;
			rightChild.child2 = gchild2;

			gchild1.data = rightList[1];
			gchild2.data = rightList[2];

			gchild1.parent = rightChild;
			gchild2.parent = rightChild;

			/*
			if(Marlon.DEBUG)
				{
				System.out.println("Setting gchild1 as "+rightList[1]);
				System.out.println("Setting gchild2 as "+rightList[2]);
				}
			*/

			}
		else
			{

			/*
			if( Marlon.DEBUG )
				{
				System.out.println("Recursing...");
				}
			*/

			//! and here we recurse...
			//! get all the triplets in the RIGHT partition...
			//! and continue...

			TripletSet rightBranch = new TripletSet();

			Enumeration e = tripVec.elements();
			while( e.hasMoreElements() )
				{
				int v[] = (int []) e.nextElement();

				//! We want all 3 of its elements to be in the left
				//! partition...so for each element check whether it
				//! is in the LEFT set...

				if( (partition[v[0]] == Graph.LEFT) || (partition[v[1]] == Graph.LEFT) || (partition[v[2]] == Graph.LEFT) )
					continue;

				//! the backscan variable ensures that the indices are correct...i.e. in
				//! the range [1...rightCount]

				rightBranch.addTriplet( rightBackMap[v[0]], rightBackMap[v[1]], rightBackMap[v[2]] );
				}

			rightChild = rightBranch.buildTree();

			if( rightChild == null ) return null;

			/*
			if( Marlon.DEBUG )
				{
				System.out.println("Past recursive step!");
				}
			*/	

			//! And now fix the leaf numbering...
			rightChild.treeFixLeaves(rightList);
			}		

		papa.child1 = leftChild;
		papa.child2 = rightChild;
		leftChild.parent = papa;
		rightChild.parent = papa;

		return papa;
		}


	}


//! ---------------------------------------------------------------------------------------
//! ---------------------------------------------------------------------------------------
//! ---------------------------------------------------------------------------------------
//! ---------------------------------------------------------------------------------------
//! ---------------------------------------------------------------------------------------


public class Marlon
        {
	public static final boolean DEBUG = false;
	public static boolean NEWICK = false;

	public static final void report( String text )
		{
		if(DEBUG) System.out.println(text);
		}

        public static void main( String[] args )
                {
		//! Need to read the triplets in from somewhere...
		TripletSet t = new TripletSet();

		if( args.length == 0 )
			{
			System.out.println("Terminating: No input file specified.");
			System.exit(0);
			}
		else
			{

			if( args.length >= 2 )
				{
				String nick = args[1];
				if( nick.equals("-d") )
					{
					biDAG r = biDAG.buildDAGfromDOT( args[0] );
					if( r != null )
						{
						r.newickDump();
						}
					else
						{
						System.out.println("Couldn't parse the DOT file, or build a DAG.");
						}
					System.exit(0);
					}
				}

			String fileName = args[0];
			int recCount = 0;

			try 	{ 
			    	FileReader fr = new FileReader(fileName);
			        BufferedReader br = new BufferedReader(fr);

			        String record = new String();
			        while ((record = br.readLine()) != null)
					{
              				recCount++;
					String[] tripData = record.split(" ");

					if( tripData.length != 3 )
						{
						System.out.println("Read line: "+record);
						System.out.println("Malformed line: each line should consist of three space-delimited integers, each greater than or equal to 1.");
						throw new IOException();
						}

					int a = Integer.parseInt(tripData[0]);
					int b = Integer.parseInt(tripData[1]);
					int c = Integer.parseInt(tripData[2]);

					if( (a==b) || (b==c) || (a==c) )
						{
						System.out.println("Read line: "+record);
						System.out.println("Each line should consist of three DISTINCT integers.");
						throw new IOException();
						}

					if( (a<=0) || (b<=0) || (c<=0) )
						{
						System.out.println("Read line: "+record);
						System.out.println("All leaves should be 1 or greater.");
						throw new IOException();
						}
	
					t.addTriplet(a,b,c);				
					}
				

           			} 
			catch (IOException e)
				{ 
		        	// catch possible io errors from readLine()
			        System.out.println("Problem reading file "+fileName);
				System.exit(0);
				}
			}


		Marlon.report("Finished reading input file.");

		if( args.length == 2 )
			{
			String nick = args[1];
			if( nick.equals("-n") )
				{
				NEWICK = true;
				}

			}

		t.finaliseAndOptimise();

		//! t.dumpTriplets();

		int errorTrip[] = new int[3];

		if( t.isClosed(errorTrip) == false )
			{
			System.out.println("Error: there are leaves in the triplet set that are unused;");
			System.out.println("Leaf "+errorTrip[0]+" does not appear in any triple (and maybe this is true for other leaves.)");
			System.out.println("Please ensure that the leaf range is precisely of the form [1...n] where all leaves in that interval appear in some triplet.");
			System.exit(0);
			}

		Marlon.report("Leaf interval is closed 1..n, good.");

		if( t.isDense(errorTrip) == false )
			{
			System.out.println("Not a dense input set.");
			System.out.println("{"+errorTrip[0]+","+errorTrip[1]+","+errorTrip[2]+"} is missing (and maybe more.)");
			System.exit(0);
			}

		Marlon.report("Triplets are dense, good.");

		Marlon.report("Attempting to build MARLON-1 network.");
		
		biDAG b = t.buildMarlon();
		
		if( b == null )
				{
				System.out.println("Was not Level 1.");
				}
			else
				{
				if( NEWICK == false )
					{
					b.dumpDAG();
					}
				else
					{
					b.newickDump();
					}
				}

                }
        }


//! ---------------------------------------------------------------------------------------
//! ---------------------------------------------------------------------------------------
//! ---------------------------------------------------------------------------------------
//! ---------------------------------------------------------------------------------------
//! ---------------------------------------------------------------------------------------


//! ----------------------
//! The root has no parent;
//! Leaves have no children, but do have data;
//! Nothing more than that...very general...can have cycles...
//! Is considered a leaf if 


class biDAG
{
public biDAG parent;
public biDAG child1, child2;
public int data;
public int dec[];
public biDAG secondParent;
public int auxDat;
public boolean visited;
public boolean simpleVisited;
public boolean fixVisit;

public boolean newickVisit;

public int newickRecNum;
public boolean newickRecVisit;

KSet snset;

public biDAG()
	{
	parent = child1 = child2 = null;
	data = 0;
	dec = null;
	secondParent = null;
	auxDat = 0;
	visited = false;
	simpleVisited = false;	//! used when counting split & recomb vertices...
	snset = null;

	newickVisit = false;
	newickRecNum = -1;
	newickRecVisit = false;
	}

//! ----------------------------------------------------------------------

public static biDAG buildDAGfromDOT( String fileName )
	{
	int recCount = 0;

	Vector left = new Vector();
	Vector right = new Vector();

	try 	{ 
	    	FileReader fr = new FileReader(fileName);
	        BufferedReader br = new BufferedReader(fr);

	        String record = new String();
	        while ((record = br.readLine()) != null)
			{
			String[] tripData = record.split(" ");

			if( tripData.length != 3 ) continue;
			if( !tripData[1].equals("->") ) continue;

			recCount++;

			int a = Integer.parseInt(tripData[0]);

			left.addElement( new Integer(a) );

			int c = Integer.parseInt(tripData[2]);

			right.addElement( new Integer(c) );

			//! System.out.println(recCount+" ::: " + a + " * " +c);
       			} 
		}
		catch (IOException e)
			{ 
	        	// catch possible io errors from readLine()
		        System.out.println("Problem reading DOT file "+fileName);
			System.exit(0);
			}

		int numEdges = left.size();

		int edges[][] = new int[numEdges][2];
		
		for( int fill = 0; fill < numEdges; fill++ )
			{
			edges[fill][0] = ((Integer)left.elementAt(fill)).intValue();
			edges[fill][1] = ((Integer)right.elementAt(fill)).intValue();
			}

	//! So, let's build it!!

	Vector dagvec = new Vector();		

	int threshhold = 1000;

	for( int e = 0; e < numEdges; e++ )
		{
		int lnum = edges[e][0];
		int rnum = edges[e][1];

		biDAG lf = findNode( dagvec, lnum );
		biDAG rf = findNode( dagvec, rnum );

		if( lf == null )
			{
			biDAG nl = new biDAG();
			if( lnum < threshhold )
				{
				nl.data = lnum;
				nl.auxDat = lnum;
				}
			else
				{
				nl.auxDat = lnum;
				}

			lf = nl;
			dagvec.addElement(nl);
			}

		if( rf == null )
			{
			biDAG nr = new biDAG();
			if( rnum < threshhold )
				{
				nr.data = rnum;
				nr.auxDat = rnum;
				}
			else
				{
				nr.auxDat = rnum;
				}
			rf = nr;
			dagvec.addElement(nr);
			}

		//! Ok, so now we're OK

		if( lf.child1 == null )
			{
			lf.child1 = rf;
			}
		else
		if( lf.child2 == null )
			{
			lf.child2 = rf;
			}
		else
			{
			System.out.println("We messed up.");
			System.exit(0);
			}

		if( rf.parent == null )
			{
			rf.parent = lf;
			}
		else
		if( rf.secondParent == null )
			{
			rf.secondParent = lf;
			}
		else
			{
			System.out.println("We messed up AGAIN.");
			}

		}

	biDAG r = findRoot( dagvec );

	return r;
	}

public static biDAG findRoot( Vector dag )
	{
	Enumeration e = dag.elements();
	while( e.hasMoreElements() )
		{
		biDAG b = (biDAG) e.nextElement();
		if( (b.parent==null) && (b.secondParent==null) )
			{
			return b;
			}
		}
	return null;
	}


public static biDAG findNode( Vector dag, int num )
	{
	if( num == 0 )
		{
		System.out.println("Not interested in nodes that have value 0.");
		System.exit(0);
		}

	Enumeration e = dag.elements();
	while( e.hasMoreElements() )
		{
		biDAG b = (biDAG) e.nextElement();
		if( b.data != 0 )
			{
			if( b.data == num ) return b;
			}
		else
			{
			if( b.auxDat == num ) return b;
			}
		}
	return null;
	}


//! We assume we have not visited the network before, which is true in the
//! case of MARLON

public void assembleNetwork( biDAG lookup[] )
	{
	if( visited == true ) return;

	visited = true;

	if( this.isLeafNode() )
		{
		KSet sub = snset;
		int subID = sub.getID();

		//! If this is a singleton SN-set we're done
		if( sub.size() == 1 )
			{
			Marlon.report("At a real leaf ("+sub.getFirstElement()+"), no labelling necessary.");
			this.data = sub.getFirstElement();
			}
		else
			{
			//! Otherwise glue the rest of the network in

			biDAG subnet = lookup[subID];
			
			if( this.parent.child1 == this )
				{
				this.parent.child1 = subnet;
				subnet.parent = this.parent;
				}
			else
			if( this.parent.child2 == this )
				{
				this.parent.child2 = subnet;
				subnet.parent = this.parent;
				}
			else
			System.out.println("Fatal flaw.");

			data = 0;

			subnet.assembleNetwork( lookup );
			}
		}
	else
		{
		if( child1 != null ) child1.assembleNetwork( lookup );
		if( child2 != null ) child2.assembleNetwork( lookup );
		}
	}

public void treeFixLeaves(int map[])
	{
	//! Changes the leaf numberings from l to map[l];
	//! Note that we assume that l>=1; 
	
	if( data != 0 ) 
		{
		if( (child1 != null) || (child2 != null) )
			{
			System.out.println("Error 4");
			}
		data = map[data];
		return;
		}
	else
		{
		child1.treeFixLeaves(map);
		child2.treeFixLeaves(map);
		return;
		}

	}

//! I only use this in MARLON and on simple level-1 networks,
//! so no need for any "we've already been here" checking...

public void buildSNCorrespondence(KSet map[])
	{
	if( this.isLeafNode() )
		{
		snset = map[data];
		//! So snset now points to the SN-set that that leaf corresponds to
		//! Marlon.report("Putting SN-set "+map[data].getID()+" in a leaf node.");
		return;
		}
	else
		{
		if( child1 != null ) child1.buildSNCorrespondence(map);
		if( child2 != null ) child2.buildSNCorrespondence(map);
		}
	}

public static biDAG makeLeafNode()
	{
	biDAG node = new biDAG();
	node.data = 1;
	return node;
	}

public static biDAG cherry12()
	{
	//! Returns a cherry, using 3 nodes,
	//! with leaf numbers 1,2.

	biDAG p = new biDAG();
	biDAG c1 = new biDAG();
	biDAG c2 = new biDAG();
	
	p.child1 = c1;
	p.child2 = c2;
	
	c1.parent = p;
	c1.data = 1;

	c2.parent = p;
	c2.data = 2;

	return p;
	}


public void dump()
	{
	if( data != 0 ) System.out.print(data);
	else
		{
		if( (child1 == null) || (child2==null) )
			{
			System.out.println("Error 5");
			if(child1 == null ) System.out.println("child1 is null");
			if(child2 == null ) System.out.println("child2 is null");
			System.exit(0);
			}
		System.out.print("[");
		child1.dump();
		System.out.print(",");
		child2.dump();
		System.out.print("]");
		}
	}
	
//! Subdivides the edge above this, creates a new leaf with element l

public biDAG insertAbove(int l)
	{
	biDAG q = new biDAG();
	biDAG c = new biDAG();				

	//! This is the 'old' parent...
	biDAG meParent = this.parent;

	c.data = l;
	c.parent = q;

	q.child1 = c;
	q.child2 = this;
	
	this.parent = q;

	if( meParent != null )
		{
		q.parent = meParent;

		if( meParent.child1 == this )
			{
			meParent.child1 = q;
			}
		else
			{
			meParent.child2 = q;
			}

		}
	else
		{
		q.parent = null;
		}

	//! That should be it......
	return c;
	}


//! This undoes what we did in the previous function....
public void removeAbove()
	{
	biDAG oldParent = this.parent.parent;
	biDAG q = this.parent;

	this.parent = oldParent;

	if( oldParent != null )
		{
		if( oldParent.child1 == q )
			{
			oldParent.child1 = this;
			}			
		else
			oldParent.child2 = this;
		}
	else
		{
		this.parent = null;
		}

	//! This will probably help garbage collection...
	q.parent = null;
	}
	
public void resetVisited()
	{
	//! Marlon.report("In resetVisited()");

	if( visited == false ) return;

	visited = false;

	if( child1 != null ) child1.resetVisited();
	if( child2 != null ) child2.resetVisited();
	}

public void newickDump()
	{
	int counter[] = new int[1];
	counter[0] = 1;

	numberRecombNodes(counter);	

	System.out.println(this.doNewick() +";");
	}

//! ---------------------------------------------------

public void numberRecombNodes( int counter[] )
	{
	if( newickRecVisit == true ) return;

	newickRecVisit = true;

	if( child1 != null )
		{
		child1.numberRecombNodes(counter);
		}

	if( child2 != null )
		{
		child2.numberRecombNodes(counter);
		}

	if( (parent != null) && (secondParent != null) )
		{
		newickRecNum = counter[0];
		counter[0]++;
		}
	return;
	}

//! --------------------------------------------------------

public String doNewick()
	{
	this.newickVisit = true;
	
	if( this.isLeafNode() )
		{
		return( this.data + "");
		}

	//! Ok, so it's either a leaf node or a recomb node...

	String lstring = null;
	String rstring = null;

	if( child1 != null )
		{
		if( child1.newickVisit == true )
			{
			lstring = "#H" + child1.newickRecNum;
			}
		else
		lstring = child1.doNewick();
		}

	if( child2 != null )
		{
		if( child2.newickVisit == true )
			{
			rstring = "#H" + child2.newickRecNum;
			}
		else
		rstring = child2.doNewick();
		}

	boolean benRecomb = ((parent != null) && (secondParent != null));

	if( (child1 != null) && (child2 != null ) )
		{
		return("(" + lstring + "," + rstring + ")");
		}
	else
	if( benRecomb )
		{
		return("(" + lstring + ")#H"+newickRecNum);
		}
	else
	System.out.println("FOUT!");

	return("BOOM!");

	}


//! This prints the dag (rooted at this node) in the funky .DOT format 
//! Still needs to be refined...NOTE THAT THIS HAS SIDE EFFECTS ON AUXDAT
//! AND VISITED SO ONLY CALL IF UNUSED OR "RESET"!!!!

public void dumpDAG()
	{
	//! Hmmm, a little bit tricky...

	int num[] = new int[1];

	//! This numbering is arbitrary, just to draw a distinction from leaves;
	num[0] = 1000;

	System.out.println("strict digraph G {");

	//! First, we'll number ALL the nodes....
	this.numVisit(num);

	//! Ok, so there is a numbering

	this.printOutgoingArcs();
	System.out.println("}");
	}

private void printOutgoingArcs()
	{
	if( child1 != null ) System.out.println( this.auxDat + " -> " + child1.auxDat );
	if( child2 != null ) System.out.println( this.auxDat + " -> " + child2.auxDat );
	this.visited = true;

	if( child1 != null )
		{
		if( child1.visited == false ) child1.printOutgoingArcs();
		}

	if( child2 != null )	
		{
		if( child2.visited == false ) child2.printOutgoingArcs();
		}

	}

private void numVisit(int num[])
	{
	//! If already been visited, finished
	if( this.auxDat != 0 ) return;

	this.auxDat = num[0];

	if( this.data != 0 )
		{
		this.auxDat = this.data;
		System.out.println(this.auxDat + " [shape=circle, width=0.3];");
		}
	else
		{
		System.out.println(this.auxDat + " [shape=point];");
		}

	num[0]++;

	if( this.child1 != null ) child1.numVisit(num);
	if( this.child2 != null ) child2.numVisit(num);
	}


//! This is hacked, might not work so well...

public boolean isLeafNode()
	{
	if( (this.child1 == null) && (this.child2 == null) )
		{
		return true;
		}
	return false;
	}

public boolean testSplit(Vector left, Vector right)
	{
	//! Tests whether it has the structure of two caterpillars with a common root
	//! and if so returns the leaf orders for left and right...from which we
	//! can compute stuff easily

	biDAG leftBranch = child1;
	biDAG rightBranch = child2;

	//! First left

	if( leftBranch.isLeafNode() )
		{
		left.addElement( leftBranch );
		}
	else
		{
		//! If it's not a leaf, then it has two children, so
		//! we can test if it's a caterpillar

		boolean check = leftBranch.testCaterpillar(left);
	
		if( !check ) return false;
		}

	//! Now the right...

	if( rightBranch.isLeafNode() )
		{
		right.addElement( rightBranch );
		}
	else
		{
		boolean check = rightBranch.testCaterpillar(right);

		if( !check ) return false;
		}

	return true;
	}


//! Tests whether it is a caterpillar and, if so, puts the
//! leaf nodes in order of visiting in Vector order. 
//! I'm going to assume that it has at least two
//! leaves....because I don't know what to do with fewer...
//! It might work with fewer leaves, but I can't guarantee it...

public boolean testCaterpillar(Vector order)
	{
	boolean finished = false;

	biDAG at = this;

	while( !finished )
		{
		//! The fact that we assume at most two leaves, and a network structure,
		//! prevents null pointer exceptions here I think

		biDAG lc = at.child1;
		biDAG rc = at.child2;

		boolean lcLeaf = lc.isLeafNode();
		boolean rcLeaf = rc.isLeafNode();

		if( (!lcLeaf) && (!rcLeaf) )
			return false;

		if( lcLeaf && rcLeaf )
			{
			//! Last two elements, order is not important...
			order.addElement(lc);
			order.addElement(rc);
			return true;
			}

		if( lcLeaf )
			{
			order.addElement(lc);
			at = rc;
			continue;
			}

		if( rcLeaf )
			{
			order.addElement(rc);
			at = lc;
			continue;
			}
		}

	return false;
	}

//! This assumes that the biDAG is a tree. Funkier things are
//! needed for DAGs...will go WRONG if it is not a tree!
//! is crude and slow, but toch

public void oneLeafAdjustTree( int correction )
	{
	if( !isLeafNode() )
		{
		if( child1 != null ) child1.oneLeafAdjustTree(correction);
		if( child2 != null ) child2.oneLeafAdjustTree(correction);
		}
	if( data >= correction ) data++;
	}

public static void glueLeafBetween( biDAG leftGraft, biDAG rightGraft, int l )
	{
	Marlon.report("In glueleafbetween");

	biDAG lb = new biDAG();
	biDAG rb = new biDAG();

	biDAG lparent = leftGraft.parent;
	biDAG rparent = rightGraft.parent;

	lb.parent = lparent;
	rb.parent = rparent;

	biDAG node = new biDAG();
	node.parent = lb;
	node.secondParent = rb;

	biDAG forgot = new biDAG();
	forgot.data = l;
	forgot.parent = node;
	node.child1 = forgot;

	lb.child1 = node;
	rb.child2 = node;

	lb.child2 = leftGraft;
	rb.child1 = rightGraft;

	leftGraft.parent = lb;
	rightGraft.parent = rb;

	if( lparent.child1 == leftGraft )
		{
		lparent.child1 = lb;
		}
	else
	if( lparent.child2 == leftGraft )
		{
		lparent.child2 = lb;
		}
	else System.out.println("ERROR#30: Something went very wrong.");

	if( rparent.child1 == rightGraft )
		{
		rparent.child1 = rb;
		}
	else
	if( rparent.child2 == rightGraft )
		{
		rparent.child2 = rb;
		}
	else System.out.println("ERROR#31: Something went very wrong...");

	Marlon.report("Finishing glue leaf between.");

	}


}