import java.util.Enumeration;
import java.io.*;
import java.util.*;
import java.lang.*;

class Graph
{
	public int v;//number of vertices
	public int adj[][];//adjacency matrix
	public boolean visited[];//for vertex i, visited[i] true if visited, false otherwise
	public int v20;//nb of nodes of indegree 2 outdegree 0
	public int v21;//nb of nodes of indegree 2 outdegree 1

	//! we'll do adj[x][y] = arc x-> y
	//! allows also multiedges (i.e. entries > 1 )

	public Graph( int vertices )
	{
		v = vertices;
		adj = new int[v][v];
		visited = new boolean[v];
	}

	public void printDot(int num,String name)
	{
		System.out.println("#"+name+"\ndigraph G_"+num+" {\n");

		for( int x=0; x<v; x++ )
			for( int y=0; y<v; y++ )
			{
				for( int s=0; s<adj[x][y]; s++ ){
					System.out.println(x+ " -> "+y);
				}
			}
		System.out.println("}");
		System.out.println();

	}


	public void dumpGraph(int num,String name)
	{
		//System.out.println("digraph G_"+num+" {");
		try{
			Generators.output.write("#"+name+"\ndigraph G_"+num+" {\n");
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		} catch (IOException e) {
			e.printStackTrace();
		}

		for( int x=0; x<v; x++ )
			for( int y=0; y<v; y++ )
			{
				for( int s=0; s<adj[x][y]; s++ ){
					//System.out.println(x+ " -> "+y);
					try{
						Generators.output.write(x+ " -> "+y+"\n");
					} catch (FileNotFoundException e) {
						e.printStackTrace();
					} catch (IOException e) {
						e.printStackTrace();
					}
				}
			}
		try{
			Generators.output.write("}\n\n");
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		} catch (IOException e) {
			e.printStackTrace();
		}
		//System.out.println("}");
		//System.out.println();

	}

	public void dumpGraph(int num)
	{
		//System.out.println("digraph G_"+num+" {");
		try{
			Generators.output.write("\ndigraph G_"+num+" {\n");
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		} catch (IOException e) {
			e.printStackTrace();
		}

		for( int x=0; x<v; x++ )
			for( int y=0; y<v; y++ )
			{
				for( int s=0; s<adj[x][y]; s++ ){
					//System.out.println(x+ " -> "+y);
					try{
						Generators.output.write(x+ " -> "+y+"\n");
					} catch (FileNotFoundException e) {
						e.printStackTrace();
					} catch (IOException e) {
						e.printStackTrace();
					}
				}
			}
		try{
			Generators.output.write("}\n\n");
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		} catch (IOException e) {
			e.printStackTrace();
		}
		//System.out.println("}");
		//System.out.println();

	}

	//All vertices of "this" in toVisit have their image in "two" defined in currentPermutation 
	public boolean recIsomorphic( Graph two , LinkedList toVisit, boolean[] visited, int nbVisited, int[] currentPermutation, boolean print)
	{
		if (print){
			System.out.println("call");
		}
		if (toVisit.isEmpty()){
			if (print){
				System.out.println("all visited:");
				for (int bloum=0;bloum<v;bloum++){
					if (visited[bloum]){
						System.out.print(" "+bloum);
					}
				}
			}

			//Check both graphs are indeed isomorphic
			int x=0;
			int y=0;
			
			/**
			for (int bloum=0;bloum<v;bloum++){
				//if (currentPermutation[bloum]==-1){
					System.out.print(" "+bloum+"->"+currentPermutation[bloum]);
				//}
			}
			printDot(1,"");
			System.out.println("and:");
			two.printDot(1,"");
			System.out.println("-------");
			**/
			while (x<v && adj[x][y]==two.adj[currentPermutation[x]][currentPermutation[y]]){
				y++;
				if (y==v){
					y=0;
					x++;
				}
			}			
			if (x<v){
				System.out.println("Bigproblem: both graphs are not isomorphic!");
				try{
					Generators.output.write("Bigproblem: both graphs are not isomorphic!");
				} catch (FileNotFoundException e) {
					e.printStackTrace();
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
			return true;
		}
		int nextVertex=0;
		
		nextVertex=(Integer) (toVisit.remove());

		

		if (print){
			System.out.println("currentVertex: "+nextVertex);
			for (int bloum=0;bloum<v;bloum++){
				if (currentPermutation[bloum]>-1){
					System.out.print(" "+bloum+"->"+currentPermutation[bloum]);
				}
			}
		}

		if (visited[nextVertex]){
			if (print){
				System.out.println("been down there"+nextVertex);
			}
			return recIsomorphic(two ,toVisit,visited,nbVisited+1,currentPermutation,print);
		}

		visited[nextVertex]=true;

		if (this.getOutDegree(nextVertex)==0){
			if (two.getOutDegree(currentPermutation[nextVertex])==0){
				if (print){
					System.out.println("been there"+nextVertex);
				}
				return recIsomorphic(two ,toVisit,visited,nbVisited+1,currentPermutation,print);
			} else {
				return false;
			}
		}

		if (print){
			System.out.println("been here");
		}
		if (this.getOutDegree(nextVertex)==1){
			if (two.getOutDegree(currentPermutation[nextVertex])==1){
				int sonThis=0;
				while(adj[nextVertex][sonThis]==0){
					sonThis++;
				}
				int sonTwo=0;
				while(two.adj[currentPermutation[nextVertex]][sonTwo]==0){
					sonTwo++;
				}
				if (currentPermutation[sonThis]>=0){
					if (currentPermutation[sonThis]!=sonTwo){
						return false;
					} else {
						toVisit.add(sonThis);
						return recIsomorphic(two ,toVisit,visited,nbVisited+1,currentPermutation,print);
					}
				} else {
					toVisit.add(sonThis);
					int delp=0;
					while (delp<v && currentPermutation[delp]!=sonTwo){
						delp++;
					}
					if (delp<v){
						return false;
					}
					currentPermutation[sonThis]=sonTwo;
					return recIsomorphic(two ,toVisit,visited,nbVisited+1,currentPermutation,print);
				}
			} else {
				return false;
			}
		} 

		if (this.getOutDegree(nextVertex)==2){
			if (two.getOutDegree(currentPermutation[nextVertex])==2){
				int sonThis1=0;
				while(adj[nextVertex][sonThis1]==0){
					sonThis1++;
				}
				int sonThis2=sonThis1+1;
				if (adj[nextVertex][sonThis1]==2){
					sonThis2=sonThis1;
				} else {
					while(adj[nextVertex][sonThis2]==0){
						sonThis2++;
					}		
				}

				int sonTwo1=0;
				while(two.adj[currentPermutation[nextVertex]][sonTwo1]==0){
					sonTwo1++;
				}

				int sonTwo2=sonTwo1+1;
				if (two.adj[currentPermutation[nextVertex]][sonTwo1]==2){
					sonTwo2=sonTwo1;
				} else {
					while(two.adj[currentPermutation[nextVertex]][sonTwo2]==0){
						sonTwo2++;
					}		
				}

				if ((sonTwo2==sonTwo1)!=(sonThis1==sonThis2)){
					return false;
				}

				if (print){
					System.out.println("SonThis1:"+sonThis1+" SonThis2:"+sonThis2+" SonTwo1:"+sonTwo1+" SonTwo2:"+sonTwo2);
				}

				if (currentPermutation[sonThis1]>=0){
					if (currentPermutation[sonThis1]==sonTwo2){
						//then sonThis2 has to be associated with sonTwo1
						if (currentPermutation[sonThis2]>=0){
							if (currentPermutation[sonThis2]==sonTwo1){
								toVisit.add(sonThis1);
								toVisit.add(sonThis2);
								return recIsomorphic(two ,toVisit,visited,nbVisited+1,currentPermutation,print);								
							} else {
								return false;
							}
						} else {
							toVisit.add(sonThis1);
							toVisit.add(sonThis2);
							int delp=0;
							while (delp<v && currentPermutation[delp]!=sonTwo1){
								delp++;
							}
							if (delp<v){
								return false;
							}
							currentPermutation[sonThis2]=sonTwo1;
							return recIsomorphic(two ,toVisit,visited,nbVisited+1,currentPermutation,print);
						}						
					} else {
						if (currentPermutation[sonThis1]==sonTwo1){
							//then sonThis2 has to be associated with sonTwo2
							if (currentPermutation[sonThis2]>=0){
								if (currentPermutation[sonThis2]==sonTwo2){
									toVisit.add(sonThis1);
									toVisit.add(sonThis2);
									return recIsomorphic(two ,toVisit,visited,nbVisited+1,currentPermutation,print);								
								} else {
									return false;
								}
							} else {
								toVisit.add(sonThis1);
								toVisit.add(sonThis2);
								int delp=0;
								while (delp<v && currentPermutation[delp]!=sonTwo2){
									delp++;
								}
								if (delp<v){
									return false;
								}
								currentPermutation[sonThis2]=sonTwo2;
								return recIsomorphic(two ,toVisit,visited,nbVisited+1,currentPermutation,print);
							}			
						} else {
							return false;
						}
					}
				} else {
					//SonThis1 has not been associated to anything yet
					//check whether sonThis2 is not associated to sth already.
					if (currentPermutation[sonThis2]>=0){
						if (currentPermutation[sonThis2]==sonTwo1){
							//then sonThis1 has to be associated with sonTwo2
							toVisit.add(sonThis1);
							toVisit.add(sonThis2);
							int delp=0;
							while (delp<v && currentPermutation[delp]!=sonTwo2){
								delp++;
							}
							if (delp<v){
								return false;
							}
							currentPermutation[sonThis1]=sonTwo2;
							return recIsomorphic(two ,toVisit,visited,nbVisited+1,currentPermutation,print);
						} else {
							//then sonThis1 has to be associated with sonTwo1
							if (currentPermutation[sonThis2]==sonTwo2){
								//then sonThis1 has to be associated with sonTwo2
								toVisit.add(sonThis1);
								toVisit.add(sonThis2);
								int delp=0;
								while (delp<v && currentPermutation[delp]!=sonTwo1){
									delp++;
								}
								if (delp<v){
									return false;
								}
								currentPermutation[sonThis1]=sonTwo1;
								return recIsomorphic(two ,toVisit,visited,nbVisited+1,currentPermutation,print);
							} else {
								return false;								
							}
						}
					} else {
						// we really have no idea which is which, so test both cases
						// sonThis1=sonTwo1 and sontThis2=sonTwo2
						// or sonThis1=sonTwo2 and sontThis2=sonTwo1
						toVisit.add(sonThis1);
						toVisit.add(sonThis2);						
						LinkedList toVisit2=(LinkedList) toVisit.clone();
						boolean[] visited2=visited.clone();
						LinkedList toVisit3=(LinkedList) toVisit.clone();
						boolean[] visited3=visited.clone();
						int[] currentPermutation2=currentPermutation.clone();
						int[] currentPermutation3=currentPermutation.clone();
						int delp=0;
						while (delp<v && currentPermutation[delp]!=sonTwo1){
							delp++;
						}
						if (delp<v){
							return false;
						}
						delp=0;
						while (delp<v && currentPermutation[delp]!=sonTwo2){
							delp++;
						}
						if (delp<v){
							return false;
						}

						currentPermutation3[sonThis1]=sonTwo1;
						currentPermutation3[sonThis2]=sonTwo2;
						currentPermutation2[sonThis1]=sonTwo2;
						currentPermutation2[sonThis2]=sonTwo1;
						boolean firstTry=recIsomorphic(two ,toVisit3,visited3,nbVisited+1,currentPermutation3,print);
						if (print){
							System.out.println("Try alternative for"+nextVertex+": "+"SonThis1:"+sonThis1+"=SonTwo2:"+sonTwo2+" & SonThis2:"+sonThis2+"=SonTwo1:"+sonTwo1);
							for (int machin=0;machin<v;machin++){
								if (visited2[machin]){
									System.out.print(machin+" ");
								}
							}
						}
						if (firstTry){
							return true;
						} else {
							return recIsomorphic(two ,toVisit2,visited2,nbVisited+1,currentPermutation2,print);
						}
					}
				}
			}
			else {
				return false;
			}
		}
		System.out.println("Noooooo! This should never happen!");
		return true;
	}

	public boolean isomorphic( Graph two )
	{
		if( v != two.v || v20 != two.v20 || v21 != two.v21) return false;
		int i=0;
		int j=0;
		while ((i<v) && (adj[i][j]==two.adj[i][j])){
			j++;
			if (j==v){
				j=0;
				i++;
			}
		}
		if(i==v){
			System.out.println("dooooooooh the exact same graph was already found");
			return true;
		} else {
			/**
			if (v<=8){

				//! Crude but effective
				int pchoose = v - 1;

				int myperm[] = new int[v];
				myperm[0] = 0;

				//! System.out.println("Scanning through perms..");

				outer: for( int scan=0; scan < Generators.perm[pchoose].length; scan++ )
				{
					for(int c=0; c < Generators.perm[pchoose][scan].length; c++ )
					{
						myperm[c+1] = Generators.perm[pchoose][scan][c] + 1;
					}


			for(int c=0; c < myperm.length; c++ )
				{
				System.out.print(myperm[c]);
				}

			System.out.println();

					for( int x=0; x<v; x++ )
						for( int y=0; y<v; y++ )
						{
							if( adj[x][y] != two.adj[myperm[x]][myperm[y]] ) continue outer;
						}


					//To check that my isomorphism algorithm gives the same result as Steven Kelk's
					LinkedList toVisit=new LinkedList();
					toVisit.add(0);
					boolean visited[]=new boolean[v];
					int[] currentPermutation = new int[v];
					currentPermutation[0]=0;
					for (int bla=1;bla<v;bla++){
						currentPermutation[bla]=-1;
					}
					for (int bla=0;bla<v;bla++){
						visited[bla]=false;
					}
					if (!recIsomorphic(two ,toVisit,visited,0,currentPermutation,false)){
						System.out.println("not isomorphic according to my method but yes in fact:");
						printDot(1,"");
						System.out.println("and:");
						two.printDot(1,"");
						System.out.println("-------");
						toVisit=new LinkedList();
						toVisit.add(0);						
						currentPermutation = new int[v];
						currentPermutation[0]=0;
						for (int bla=1;bla<v;bla++){
							currentPermutation[bla]=-1;
						}
						for (int bla=0;bla<v;bla++){
							visited[bla]=false;
						}
						recIsomorphic(two ,toVisit,visited,0,currentPermutation,true);
					}


					return true;


				}

				LinkedList toVisit=new LinkedList();
				toVisit.add(0);
				boolean visited[]=new boolean[v];
				int[] currentPermutation = new int[v];
				currentPermutation[0]=0;
				for (int bla=1;bla<v;bla++){
					currentPermutation[bla]=-1;
				}
				for (int bla=0;bla<v;bla++){
					visited[bla]=false;
				}
				if (recIsomorphic(two ,toVisit,visited,0,currentPermutation,false)){
					System.out.println("isomorphic according to my method but not in fact:");
					printDot(1,"");
					System.out.println("and:");
					two.printDot(1,"");
					System.out.println("-------");
					toVisit=new LinkedList();
					toVisit.add(0);

					currentPermutation = new int[v];
					currentPermutation[0]=0;
					for (int bla=1;bla<v;bla++){
						currentPermutation[bla]=-1;
					}
					for (int bla=0;bla<v;bla++){
						visited[bla]=false;
					}
					recIsomorphic(two ,toVisit,visited,0,currentPermutation,true);
				}

				return false;
			} else {
			 **/

			LinkedList toVisit=new LinkedList();
			toVisit.add(0);
			boolean visited[]=new boolean[v];
			
			int[] currentPermutation = new int[v];
			currentPermutation[0]=0;
			for (int bla=1;bla<v;bla++){
				currentPermutation[bla]=-1;
			}
			for (int bla=0;bla<v;bla++){
				visited[bla]=false;
			}
			
			
			boolean answer=recIsomorphic(two ,toVisit,visited,0,currentPermutation,false);
			return answer;
		}
	}



	//! a DAG is connected iff every vertex except vertex 0 has indegree at least 1

	public boolean connected()
	{
		//! Don't bother with vertex 0;
		for( int y=1; y<v; y++ )
		{
			//! Check if some vertex links to you...

			if( getInDegree(y) == 0 ) return false;
		}
		return true;
	}

	//! Does an undirected spanning tree from vertex ver, updating seenVec, and avoiding 'avoid'

	private void bvisit( int ver, boolean seenVec[], int avoid )
	{
		if( seenVec[ver] ) return;

		seenVec[ver] = true;

		int children[] = new int[3];
		int at = 0;

		if(Lev3Gen.DEBUG) System.out.println("At vertex "+ver+", trying to avoid "+avoid);

		for( int y=0; y<v; y++ )
		{
			if( adj[ver][y] != 0 )
			{
				children[at++] = y;
				if(Lev3Gen.DEBUG) System.out.println("Adding out child "+y);
			}
		}

		for( int x=0; x<v; x++ )
		{
			if( adj[x][ver] != 0 )
			{
				children[at++] = x;
				if(Lev3Gen.DEBUG) System.out.println("Adding in child "+x);
			}
		}
		//! System.out.println("Done.");

		for( int c=0; c<at; c++ )
		{
			if( children[c] != avoid ) bvisit(children[c],seenVec, avoid);
		}		

	}

	public boolean biconnected()
	{
		//! cycle through the vertices, one at at time, suppressing them...

		boolean svec[] = new boolean[v];

		boolean bic = true;

		galaxy: for( int s=0; s<v; s++ )
		{
			for(int x=0; x<svec.length; x++ ) svec[x] = false;

			if(Lev3Gen.DEBUG) System.out.println("Suppressing "+s);

			int start = -1;
			for( int f=0; f<v; f++ )
			{
				if( f != s )
				{
					start = f;
					break;
				}
			}
			if(Lev3Gen.DEBUG) System.out.println("Starting at vertex "+start);

			bvisit( start, svec, s );

			/*
			for(int p=0; p<svec.length; p++ )
				{
				if(Lev3Gen.DEBUG) System.out.print(svec[p]+" ");
				}
			System.out.println();
			 */	

			for( int x=0; x<svec.length; x++ )
			{
				if( (svec[x]==false) && (x != s) )
				{
					bic = false;
					break galaxy;
				}
			}			

		}		
		return bic;
	}

	public int getInDegree( int p )
	{
		int total = 0;
		for( int x=0; x<v; x++ ) total += adj[x][p];

		return total; 
	}

	public int getOutDegree( int p )
	{
		int total = 0;
		for( int y=0; y<v; y++ ) total += adj[p][y];

		return total;
	}


	public boolean isRoot(int p)
	{
		return( (getInDegree(p)==0) && (getOutDegree(p)==2) );
	}

	public boolean isSplit(int p)
	{
		return( (getInDegree(p)==1) && (getOutDegree(p)==2) );
	}


	//! Note that this is a GENERATOR recomb node i.e. outdeg <= 1
	public boolean isRecomb(int p)
	{
		return( (getInDegree(p)==2) && (getOutDegree(p) <= 1) );
	}

	public Graph augment(int delta)
	{
		Graph newGraph=new Graph(v+delta);
		newGraph.v20=v20;
		newGraph.v21=v21;
		newGraph.visited = new boolean[v+delta];
		for(int i=0;i<v;i++){
			for(int j=0;j<v;j++){
				newGraph.adj[i][j]=adj[i][j];
			}
		}
		for(int i=0;i<v+delta;i++){
			for(int j=v;j<v+delta;j++){
				newGraph.adj[i][j]=0;
			}
		}
		for(int i=v;i<v+delta;i++){
			for(int j=0;j<v+delta;j++){
				newGraph.adj[i][j]=0;
			}
		}
		return newGraph;
	}

	public void unvisit()
	{
		for( int x=0; x<v; x++ ) visited[x]=false;
	}

	//Answers true if there exists a directed path from u to v
	public boolean directedPath(int u, int v)
	{
		unvisit();
		return recDirectedPath(u,v);
	}

	public boolean recDirectedPath(int i, int j)
	{
		if (!visited[i]){
			visited[i]=true;
			if (i==j){
				return true;
			} else {
				boolean found = false;
				int x=0;
				while ((x<v) && !found){
					if (adj[i][x]>0){
						if (recDirectedPath(x,j)) {
							found=true;
						}
					}
					x++;
				}
				return found;
			}
		}
		else
			return false;
	}

	//Determines whether the graph is isomorphic to one of those in graphs
	public boolean containedIn(Vector graphs){
		Enumeration enoom = graphs.elements();
		boolean isnew = true;

		int i=5;
		nogood: while( enoom.hasMoreElements() ){
			Graph two = (Graph) enoom.nextElement();
			if( this.isomorphic( two ) ){
				isnew = false;
				System.out.println("nope, G_"+(graphs.size()+1)+" isomorphic to G_"+(i));
				break nogood;
			}
			i++;
		}
		return (!isnew);
	}


	//Rule R1 applied to 2 arcs.
	//If both arcs link the same nodes, they
	//are considered to be the same one
	//=> use ruleR1multi if it's not the case
	public void ruleR1(int e1i, int e1j, int e2i, int e2j)
	{
		//3 nodes have been added, 2 split and 1 recomb

		if ((e1i==e2i) && (e1j==e2j)){
			//R1 performed on one same edge
			adj[e1i][e1j]=adj[e1i][e1j]-1;
			adj[e1i][v-3]=1;	   
			adj[v-3][v-2]=1;	   
			adj[v-2][e1j]=1;	   
		} else {
			adj[e1i][e1j]=adj[e1i][e1j]-1;
			adj[e2i][e2j]=adj[e2i][e2j]-1;
			adj[e1i][v-3]=1;	   
			adj[e2i][v-2]=1;	   
			adj[v-3][e1j]=1;	   
			adj[v-2][e2j]=1;	   
		}
		adj[v-3][v-1]=1;
		adj[v-2][v-1]=1;
	}

	//Rule R2 applied to 2 arcs.
	//If both arcs link the same nodes, they
	//are considered to be the same one
	//=> use ruleR2multi if it's not the case
	public void ruleR2(int e1i, int e1j, int e2i, int e2j)
	{
		//2 nodes have been added, 1 split and 1 recomb

		if ((e1i==e2i) && (e1j==e2j)){
			//R2 performed on one same edge
			adj[e1i][e1j]=adj[e1i][e1j]-1;
			adj[e1i][v-2]=1;	   
			adj[v-2][v-1]=2;	   
			adj[v-1][e1j]=1;	   
		} else {
			adj[e1i][e1j]=adj[e1i][e1j]-1;
			adj[e2i][e2j]=adj[e2i][e2j]-1;
			adj[e1i][v-2]=1;	   
			adj[e2i][v-1]=1;	   
			adj[v-2][e1j]=1;	   
			adj[v-1][e2j]=1;	   
			adj[v-2][v-1]=1;
		}
	}


	//Rule R1 applied to 2 different arcs which link the same nodes
	public void ruleR1multi(int e1i, int e1j, int e2i, int e2j)
	{
		if ((e1i==e2i) && (e1j==e2j)){
			//3 nodes have been added, 2 split and 1 recomb
			adj[e1i][e1j]=0;
			adj[e1i][v-3]=1;	   
			adj[e1i][v-2]=1;	   
			adj[v-3][e1j]=1;	   
			adj[v-2][e1j]=1;	   
			adj[v-3][v-1]=1;
			adj[v-2][v-1]=1;
		}
	}

	//Rule R2 applied to 2 different arcs which link the same nodes
	public void ruleR2multi(int e1i, int e1j, int e2i, int e2j)
	{
		if ((e1i==e2i) && (e1j==e2j)){
			//2 nodes have been added, 1 split and 1 recomb
			adj[e1i][e1j]=0;
			adj[e1i][v-2]=1;	   
			adj[e1i][v-1]=1;	   
			adj[v-2][e1j]=1;	   
			adj[v-1][e1j]=1;	   
			adj[v-1][v-2]=1;
		}
	}

	//Rule R1 applied to a hybrid node and an arc
	public void ruleR1(int i,int ei, int ej)
	{
		//1 recomb node is attached below hybrid node i and arc e=(ei,ej)
		adj[ei][ej]=adj[ei][ej]-1;
		adj[ei][v-2]=1;
		adj[v-2][ej]=1;
		adj[v-2][v-1]=1;		
		adj[i][v-1]=1;		
	}

	//Rule R2 applied to a hybrid node and an arc
	public void ruleR2(int i,int ei, int ej)
	{
		//1 recomb node is inserted below hybrid node i inside arc e=(ei,ej)
		adj[ei][ej]=adj[ei][ej]-1;
		adj[ei][v-1]=1;
		adj[v-1][ej]=1;
		adj[i][v-1]=1;		
	}

	//Rule R1 applied to 2 different hybrid nodes
	public void ruleR1(int i, int j)
	{
		//1 recomb node is attached below 2 hybrid nodes
		adj[i][v-1]=1;
		adj[j][v-1]=1;
	}

}