class ThreeCaterpillars
	{
	int c1 = 0;
	int c2 = 0;
	int c3 = 0;
	
	public ThreeCaterpillars(int a, int b, int c)
		{
		c1 = a;
		c2 = b;
		c3 = c;
		}

	//! Ignores the last two elements because their order can always be permuted;
	static public boolean match( int x, int y )
		{
		for(int s = 2; s< FindGadget.p[x].length; s++)
			{
			if( FindGadget.p[x][s] != FindGadget.p[y][s] ) return false;
			}
		return true;
		
		}
		
	public boolean sameAs( ThreeCaterpillars two )
		{
		if( match( c1, two.c1) && match( c2, two.c2) && match( c3, two.c3) ) return true;
		if( match( c1, two.c1) && match( c2, two.c3) && match( c3, two.c2) ) return true;

		if( match( c1, two.c2) && match( c2, two.c1) && match( c3, two.c3) ) return true;
		if( match( c1, two.c2) && match( c2, two.c3) && match( c3, two.c1) ) return true;
		
		if( match( c1, two.c3) && match( c2, two.c1) && match( c3, two.c2) ) return true;
		if( match( c1, two.c3) && match( c2, two.c2) && match( c3, two.c1) ) return true;
		
		return false;
		}
			
		
	public boolean containsTriplet( int a, int b, int c )
		{
		if( FindGadget.catContainsTrip( c1, a, b, c ) ) return true;
		if( FindGadget.catContainsTrip( c2, a, b, c ) ) return true;
		if( FindGadget.catContainsTrip( c3, a, b, c ) ) return true;
		return false;	
		}

	public void dumpTriplets()
		{
		int t = FindGadget.taxa;
		for(int a=0; a<t; a++)
		for(int b=0; b<t; b++)
		for(int c=0; c<t; c++)
			{
			if( (a==b) || (b==c) || (a==c) ) continue;
			if( a > b ) continue;
			if( containsTriplet(a,b,c) )
				{
				System.out.println(a+" "+b+" "+c);
				}
			}
		
		}

	public void dumpTripletsMiniZinc()
		{
		int t = FindGadget.taxa;
		int count = 0;
		for(int a=0; a<t; a++)
		for(int b=0; b<t; b++)
		for(int c=0; c<t; c++)
			{
			if( (a==b) || (b==c) || (a==c) ) continue;
			if( a > b ) continue;
			if( containsTriplet(a,b,c) )
				{
				System.out.println(a+","+b+","+c+",");
				count++;
				}
			}

		System.out.println("int: numtrips = "+count);
		}

		
	public boolean satisfiedBy( ThreeCaterpillars two )
		{
		int t = FindGadget.taxa;
		for(int a=0; a<t; a++)
		for(int b=0; b<t; b++)
		for(int c=0; c<t; c++)
			{
			if( (a==b) || (b==c) || (a==c) ) continue;
			if( a > b ) continue;
			if( containsTriplet(a,b,c) )
					{
					if( two.containsTriplet(a,b,c) == false)
						{
						return false;
						}
					}
			}
		return true;			
		}

	}
		


public class FindGadget
{
public static void dumpCaterpillar(int catNum)
	{
	for( int x=0; x<p[catNum].length; x++)
		{
		System.out.print(p[catNum][x]);
		}
	System.out.println();
	}


public static boolean catContainsTrip(int catNum, int a, int b, int c)
	{
	//!System.out.println("Checking triplet "+a+b+"|"+c+" in permutation:");
	//!for(int x=0; x<p[catNum].length; x++) System.out.print(p[catNum][x]);
	//! System.out.println();
	if( (pos[catNum][a] < pos[catNum][c]) && (pos[catNum][b] < pos[catNum][c]) )
		{
		//! System.out.println("TRUE!");
		return true;
		}
	else
		{
		//! System.out.println("FALSE!");
		return false;
		}
	
	}

static int p[][];

static int pos[][];

static int taxa = -1;

static boolean uniqueExists = false;

public static void main(String args[])
	{
	taxa = 6;

	System.out.println("Going to look for unique caterpillars on "+taxa+" taxa.");

	
	int perm = 1;
	for(int loop=taxa; loop>=1; loop--)
		{
		perm = perm * loop;
		}
		
	System.out.println("First, generating all possible "+perm+" permutations of "+taxa+" taxa...");

	p = new int[perm][taxa];
	
	pos = new int[perm][taxa];
	
	int at = 0;

	int counter[] = new int[taxa];

	while( at < p.length )
		{
		boolean seen[] = new boolean[taxa];
		for(int x=0; x<seen.length; x++) seen[x] = false;
		
		for(int x=0; x<counter.length; x++) seen[ counter[x] ]=true;
			
		boolean good = true;
		for(int x=0; x<seen.length; x++)
			{
			if(seen[x] == false)
				{
				good = false;
				break;
				}
			}
	
		if( good )
			{
			System.out.print(at+": ");
			for(int x=0; x<counter.length; x++)
					{
					p[at][x] = counter[x];
					System.out.print(counter[x]);
					pos[at][counter[x]] = x;
					}

			System.out.println();
			at++;
			}
			
		int ptr = counter.length-1;
		while( ptr >= 0 )
			{
			if( counter[ptr] < (taxa-1) )
				{
				counter[ptr]++;
				break;
				}
			else
				{
				counter[ptr]=0;
				ptr--;
				}
			}
			
		}

	System.out.println("Found "+at+" permutations.");	
	
	System.out.println("Starting search for uniquely defined caterpillars.");

	int x = 0;	//! Assume that the first caterpillar is 0123...
	for( int y = 107; y<perm; y++)
	for( int z = 233; z<perm; z++)
		{
		ThreeCaterpillars tc = new ThreeCaterpillars(x,y,z);
		System.out.println("Checking: "+x+" "+y+" "+z);
		
		/*
		System.out.println("Checking the following caterpillars for uniqueness:");
		dumpCaterpillar(x);
		dumpCaterpillar(y);
		dumpCaterpillar(z);
		*/
		
		boolean unique = true;
		
		outer: for(int d=0; d<perm; d++)
		for(int e=0; e<perm; e++)
		for(int f=0; f<perm; f++)
			{
			ThreeCaterpillars two = new ThreeCaterpillars(d,e,f);
			if( tc.sameAs(two) ) continue;
			
			if( tc.satisfiedBy(two) )
				{
				/*
				System.out.println("NOT UNIQUE BECAUSE THESE CATERPILLARS ALSO CONTAIN ALL THE TRIPLETS:");

				dumpCaterpillar(d);
				dumpCaterpillar(e);
				dumpCaterpillar(f);
				*/


				unique = false;
				break outer;
				}
			}
		if( unique )
			{
			System.out.println("THE FOLLOWING THREE CATERPILLARS ARE UNIQUELY DEFINED (UP TO SYMMETRY OF TWO LEFTMOST TAXA)!");
			System.out.println("Code ="+x+" - "+y+" - "+z);
			
			uniqueExists = true;
			
		dumpCaterpillar(x);
		dumpCaterpillar(y);
		dumpCaterpillar(z);
			
		System.out.println("-- Triplets --");
		tc.dumpTriplets();	
		System.out.println("--------------");
		tc.dumpTripletsMiniZinc();
		
			//! Comment this line out to get more unique caterpillars
			System.exit(0);
			}
		}
	
	if( !uniqueExists )
		{
		System.out.println("NO UNIQUE CATERPILLARS FOUND ON "+taxa+" TAXA :-(");
		
		}
	
		
	}






}