// orthogonal.cpp : Defines the entry point for the console application.
//

//#include "stdafx.h"
#include<algorithm>
#include<iostream>
#include <stdlib.h>
#include <conio.h>
#include<math.h>
#include<cstring>
#include<string.h>
using std::cout;
using std::cin;
using namespace std;
static long int fr[' '];
static long int countk =0;
static long int flagh =0;
static long int edge=0;
static long int hcount=0;
static long int s1=0;
static long int s2=0;
//string up;
struct
{
long int a[' '];
long int b[' '];
}m2;

struct
{
long int a[' '];
long int b[' '];
}m1;
FILE *fp2=fopen("patternk.dat","w");

class node;
struct list
{
	node *N;
	list *Next;
};
class node
{
	private:
		int *p;
		int max;
	public:
		node(int tsize);
		~node();
		void setvalue(int pos,int X, int Y);
		void displaylist();
		int size();
		void printlist(FILE*fp);
		int issame(node*T);
		int getX(int pos);
		int getY(int pos);
};
node::node(int tsize)
{
	max=tsize;
	p=new int[max*2];
	for(int i=0; i<max;i++) {*(p+(i*2))=0;*(p+(i*2)+1)=0;}
}
node::~node()
{
	delete p;
}
void node::setvalue(int pos,int X, int Y)
{
	if(pos<max)
	{
		*(p+(2*pos))=X;
		*(p+(2*pos)+1)=Y;
	}
}
void node::displaylist()
{
	printf("{");
	for(int i=0; i<max; i++)
	{
		printf("[%d,%d]",*(p+(i*2)),*(p+(i*2)+1));
		if(i!=max-1) {printf(",");}
	}
	printf("}");
}
int node::size()
{
	return max;
}
void node::printlist(FILE *fp)
{
	fprintf(fp,"{");
	for(int i=0;i<max;i++)
	{
		fprintf(fp,"[%d,%d]",*(p+(i*2)),*(p+(i*2)+1));
		if(i!=max-1){fprintf(fp,",");}
				printf("[%d,%d]",*(p+(i*2)),*(p+(i*2)+1));
		if(i!=max-1){printf(",");}
	}
	fprintf(fp,"}");
}
int node::issame(node *T)
{
	//1-true; 0=false;
	int Count=0;
	if(max==T->size())
	{
		for(int i=0; i<max; i++)
		{
			for(int j=0;j<max;j++)
			{
				if((T->getX(i)==this->getX(j))&&(T->getY(i)==this->getY(j)))
				{
					Count++;
				}
				else if((T->getX(i)==this->getY(j))&&(T->getY(i)==this->getX(j)))
				{
					Count++;
				}
			}
		}
		if(Count==max)
			return 1;
		else
			return 0;
	}
	else
	{
		return 0;
	}
}
int node::getX(int pos)
{
	return *(p+(pos*2));
}
int node::getY(int pos)
{
	return *(p+(pos*2)+1);
}
class nodelist
{
	private:
				void delnodes(list *r);
	public:
	    list *root;
		list *last;
		nodelist();
		~nodelist();
		void addnode(node *Nd);
		list *addnodesub(list *p,node *nd);
		int IsinList(node *Nd);
		void printlist(FILE *p);
		long int ListSize();
};
nodelist::nodelist()
{
	root=NULL;last=NULL;
}
nodelist::~nodelist()
{
	delnodes(root);
}
void nodelist::delnodes(list *r)
{
	if(r!=NULL)
	{
		delnodes(r->Next);
		delete(r->Next);
	}
}
list * nodelist::addnodesub(list *p,node *nd)
{
	if(p==NULL)
	{
		p=new list;
		p->N=nd;
		p->Next=NULL;
	}
	else
	{
		p->Next=addnodesub(p->Next,nd);
	}
	return p;
}
void nodelist::addnode(node *Nd)
{
	root=addnodesub(root,Nd);
}
int nodelist::IsinList(node *Nd)
{
	list *Temp;
	for(Temp=root;Temp!=NULL; Temp=Temp->Next)
	{
		if(Temp->N->issame(Nd)==1)
		{
			return 1;
		}
	}
	return 0;
}
void nodelist::printlist(FILE *p)
{
	list *Temp;
	for(Temp=root;Temp!=NULL;Temp=Temp->Next)
	{
		(Temp->N)->printlist(p);
		fprintf(p,"\n");
		printf("\n");
	}
}
long int nodelist::ListSize()
{
	long int Ret=0;
	list *Temp;
	for(Temp=root;Temp!=NULL;Temp=Temp->Next)
	{
		Ret++;
	}
	return Ret;
}

//FILE *fp2=fopen("patterng.doc","w+");;

template <class BidIt>

bool next_combination(BidIt n_begin, BidIt n_end,
BidIt r_begin, BidIt r_end)
{
  
  bool boolmarked=false;
  BidIt r_marked;
  
  BidIt n_it1=n_end;
  --n_it1;
  
  
  BidIt tmp_r_end=r_end;
  --tmp_r_end;
  BidIt tmp_r_begin=r_begin;
  --tmp_r_begin;
  
  for(BidIt r_it1=tmp_r_end; r_it1!=tmp_r_begin ; --r_it1,--n_it1)
  {
    if(*r_it1==*n_it1 )
    {
      if(r_it1!=r_begin) //to ensure not at the start of r sequence
      {
        boolmarked=true;
        r_marked=(--r_it1);
        ++r_it1;//add it back again 
        continue;
      }
      else // it means it is at the start the sequence, so return false
        return false;      
    }
    else //if(*r_it1!=*n_it1 )
    {
      //marked code
      if(boolmarked==true)
      {
        //for loop to find which marked is in the first sequence
        BidIt n_marked;//mark in first sequence
        for (BidIt n_it2=n_begin;n_it2!=n_end;++n_it2)
          if(*r_marked==*n_it2) {n_marked=n_it2;break;}
      
    
        BidIt n_it3=++n_marked;    
        for  (BidIt r_it2=r_marked;r_it2!=r_end;++r_it2,++n_it3)
        {
          *r_it2=*n_it3;
        }
        return true;
      }
      for(BidIt n_it4=n_begin; n_it4!=n_end; ++n_it4)
        if(*r_it1==*n_it4)
        {
          *r_it1=*(++n_it4);
          return true;           
        }
    }
  }  

  return true;//will never reach here    
}
      
int main(int argc, char* argv[])
{
     long int n1,z[' '];
     long int n,b,b1,adj[' '][' '],adj1[' '][' '];
long int i,j,edge1;
  long int ve[' '],ve2[' '];
nodelist *NL;
long int cnt;
node *xn;
   edge=0;
NL = new nodelist();
    cout<<"Enter the number of verticies of the base graph \n";
    cin>>n1;
    cout<<"\n Enter the Adjacency Matrix of the base graph:\n";
    for(i=0;i<n1;i++)
    z[i]=i;
    for(i=0;i<n1;i++)
       for(j=0;j<n1;j++)
	 {
	     if(i!=j)
	   adj1[i][j]=1;
	   if(adj1[i][j])
	    edge1++;
	  }    
	  
    for(i=0;i<n1;i++)
       for(j=i+1;j<n1;j++)
	 {
	  	   if(adj1[i][j])
	   {
	       m1.a[s1]=z[i];
	       m1.b[s1]=z[j];
	       s1++;
	      	  }    
	  else
	  {
	      m2.a[s2]=z[i];
	      m2.b[s2]=z[j];
	      s2++;
	  }    
	 }
	    
	    edge1=edge1/2;
  cout<<"\nEnter the No.of Vertices:";
  cin>>n;
  cout<<"\n Enter the Adjacency Matrix:\n";
      for(i=0;i<n;i++)
       for(j=0;j<n;j++)
	 {
	   cin>>adj[i][j];
          if(adj[i][j])
	      edge++;
	 }
	 edge=edge/2;
   b=edge1+1;
   b1=edge+1;
   for(i=0;i<=edge;i++)
   ve[i]=i;
     for(i=0;i<n;i++)
	   ve2[i]=i;
   do
   {
	   do
	   {
        
		long int i,j,k,flag,flagr,z1=0;
		flag=0;
		flagr=0;
		fflush(stdin);

	     for(i=0;i<n;i++)
	       for(j=i+1;j<n;j++)
	    if(adj[i][j]==1)
	    {
          for(long int x1=0;x1<s2;x1++)
          {
              flag=0;
              if(((m2.a[x1]==ve[i])&&(m2.b[x1]==ve[j]))||((m2.b[x1]==ve[i])&&(m2.a[x1]==ve[j])))
              	flag=1;
              	if(flag==1)
              	{
              	    z1=1;
              	    goto c;
              	}
           }
       }            
c:         
    flag=0;    
          
	    if(z1==0)
	    {

     cnt=0;
     xn = new node(edge);  
    for(i=0,k=0;i<n;i++)
	    for(j=i+1;j<n;j++)
	    {
	    if(adj[i][j]==1)
	    {
            xn->setvalue(cnt,ve[i],ve[j]);
	      cnt++;		 
	       k++;
		      }
	      }
	       if(NL->IsinList(xn)==0)
	          {
	          NL->addnode(xn);
	      		
		
}	
}
	              
    }while ( next_permutation(ve,ve+n));
    }while ( next_combination(ve,ve+edge+1,ve2,ve2+n) );
  //   combinations(lab,0,b,0,n-1);
	fflush(stdin);
	flagh=1;
//	cout<<"check"<<up<<endl;
	cout<<NL->ListSize();
		for(i=0;i<NL->ListSize();i++)
  ve[i]=i;
  for(i=0;i<=edge;i++)
  fr[i]=i;
  
  	do
	{
do
{
     long int r1,r2,r4,r6,r5,r8,flag=0,flagr=0,flagt=0,flagd=0;
    
	for(r1=0;r1<n;r1++)
    {
           for(r2=0;r2<n;r2++)
    {
    flagt=0;
    flag=0;
       if(r1!=r2)
    {
        flagd=0;
        for(r5=0;r5<s2;r5++)
        if(((m2.a[r5]==r1)&&(m2.b[r5]==r2))||((m2.a[r5]==r2)&&(m2.b[r5]==r1)))
        {
        flagd=1;
        break;
    }
     if(flagd==1)
     {       
         list *temp1;
         list *temp2;
	//	  cout<<"running";
          for(temp1=NL->root,r4=0;r4<fr[r1];r4++,temp1=temp1->Next);
           for(temp2=NL->root,r4=0;r4<fr[r2];r4++,temp2=temp2->Next);  
       
	//	   NL->printlist(fp2);
      //         printf("\n");
		//	   getch();
      for(r4=0;r4<edge;r4++)
    {
       for(r6=0;r6<edge;r6++)
       {
      if(((temp1->N)->getX(r4)==(temp2->N)->getX(r6))&&((temp1->N)->getY(r4)==(temp2->N)->getY(r6)))
            {
            flagt=1;
              }
              if((temp1->N)->getX(r4)==(temp2->N)->getY(r6))
              if((temp1->N)->getY(r4)==(temp2->N)->getX(r6))
      {
               flagt=1;
              }
       }
       }

          if((flagt!=0)&&(r1!=r2))
       {
       flag=1;
       flagt=0;
       goto b;
              }

       }
       
       
 if(flagd==0)
     {           
         flag=0;
         flagt=0;
         list *temp1;
         list *temp2;
		 	// cout<<"running";
            //NL->printlist(fp2);
              // printf("\n");
			  // getch();
                  for(temp1=NL->root,r4=0;r4<fr[r1];r4++,temp1=temp1->Next);
           for(temp2=NL->root,r4=0;r4<fr[r2];r4++,temp2=temp2->Next);
            for(r4=0;r4<edge;r4++)
    {
       for(r6=0;r6<edge;r6++)
       {
      if(((temp1->N)->getX(r4)==(temp2->N)->getX(r6))&&((temp1->N)->getY(r4)==(temp2->N)->getY(r6)))
      {
            flagt++;
             }
             if(((temp1->N)->getX(r4)==(temp2->N)->getY(r6))&&((temp1->N)->getY(r4)==(temp2->N)->getX(r6)))
             {
            flagt++;
             }
       
       }
       }

         if((flagt!=1)&&(r1!=r2))
       {
       flag=1;
       flagt=0;
//	   NL->printlist(fp2);
       goto b;
              }

       }
      
       }
}
}
    b:  

      fflush(stdin);
      
      if(flag==0)
       {
       flagr=1;
       	 for(r8=0;r8<=edge;r8++)
	 {
	     list *temp1;
	// fprlong intf(fp2,"%d{",fr[r8]);
		 printf("\n");
	cout<<"{"<<fr[r8];
	long int dl;
	              for(dl=0,temp1=NL->root;dl<fr[r8];dl++,temp1=temp1->Next);
	       /*for(r7=0;r7<edge;r7++)
		{
	   //fprlong intf(fp2,"(%d , %d),  ",m[fr[r8]].a[r7],m[fr[r8]].b[r7]);
	cout<<"("<< (temp1->N)->getX(r7)<<","<<(temp1->N)->getX(r7)<<"),";
	}
	//fprlong intf(fp2,"}\n");
	cout<<"}\n";
	}*/
				  (temp1->N)->printlist(fp2);
				  printf("\n");
			 }
		 cout<<"NEXT \n\n";
	//fprlong intf(fp2,"NEXT \n\n");
	getch();
	hcount++;
	       }

     
     
 }while ( next_permutation(ve, ve + edge+1 ) );
}while ( next_combination(ve, ve + NL->ListSize() ,fr,fr+edge+1) );
	
	

//cout<<"complete"<<up;
	getch();
	return(0);
	}