// Please read "readme.txt" first.

#include<stdio.h>
#include<math.h>
#include <stdlib.h> 
#include <iostream>
#include <algorithm>
using namespace std;

int SizeOfMatrix,NumberOfRandomMutations,NumberOfAnswer;
int Matrix[40][40],NumberOfMatrix,NumberOf2p,NumberOf3,NumberOf4p,NumberOf2m,NumberOf4m;
FILE* f, * file;
char  line[100], NameOfInput[100],NameOfOutput[100]; 


void copy_matrix(int M[40][40], int M1[40][40], int dim){ 
 for(int i=1;i<=dim;i++)
  for(int j=1;j<=dim;j++)
   M1[i][j]=M[i][j];
}
	
void write_submatrix(int M[40][40], int M1[40][40], int dim, int k){ //writes matrix M to M1 removing k-th string and column
 int e1=0;
 int e2=0;
 for(int i=1;i<=dim-1;i++){
  e2=0;
  if(i==k)
    e1=1;
  for(int j=1;j<=dim-1;j++){
   if(j==k)
    e2=1;
   M1[i][j]=M[i+e1][j+e2];
  }
 }
}

void print_matrix(){
 f=fopen(NameOfOutput,"a");
 fprintf(f," %d", NumberOfMatrix);
 fclose(f);
}

void print_last_line(int M1[40][40]){
 f=fopen(NameOfOutput,"a");
 fprintf(f,"\n  %d   SizeOfMatrix=%d  NumberOfMatrix=%d   NewValenciesLine=  " , NumberOfAnswer,SizeOfMatrix,NumberOfMatrix);
 for(int i=1;i<=SizeOfMatrix;i++)
   if(M1[SizeOfMatrix+1][i]>=0)  fprintf(f,"  %d",M1[SizeOfMatrix+1][i]);
   else fprintf(f," %d",M1[SizeOfMatrix+1][i]);
 fprintf(f,"\n");
 fclose(f);
}

void print_last_column(int M1[40][40]){
 f=fopen(NameOfOutput,"a");
 fprintf(f,"\n  %d   SizeOfMatrix=%d  NumberOfMatrix=%d   NewValenciesColumn=  " , NumberOfAnswer,SizeOfMatrix,NumberOfMatrix);
 for(int i=1;i<=SizeOfMatrix;i++)
   if(M1[i][SizeOfMatrix+1]>=0)  fprintf(f,"  %d",M1[i][SizeOfMatrix+1]);
   else fprintf(f," %d",M1[i][SizeOfMatrix+1]);
 fprintf(f,"\n");
 fclose(f);
}

int sgn(int a){
  if(a>0)  return 1;
  if(a==0) return 0;
  if(a<0)  return -1; 
}

void mutation(int M1[40][40],int dim,int k){
 int M2[40][40];
 copy_matrix(M1,M2,dim);
 for(int i=1;i<=dim;i++)
  for(int j=1;j<=dim;j++)
   M1[i][j]=-M2[i][j]*(1-abs(sgn((i-k)*(j-k))))+(M2[i][j]+sgn(M2[i][k])*max(0,M2[i][k]*M2[k][j]))*abs(sgn((i-k)*(j-k))); 
}

bool nonmin_infinite(){
 int i,k,M1[40][40];
 for(i=1;i<=SizeOfMatrix+1;i++){
  write_submatrix(Matrix,M1,SizeOfMatrix+1,i);
  k=SizeOfMatrix;
  mutation(M1,SizeOfMatrix,k);
  for(int i=2;i<=SizeOfMatrix;i++)
   for(int j=1;j<=i-1;j++)
    if(abs(M1[i][j])*abs(M1[j][i])>4)
     return true;
  for(int i=1;i<=NumberOfRandomMutations;i++){
   k=(rand() % (SizeOfMatrix))+1;
   mutation(M1,SizeOfMatrix,k);
   for(int i=2;i<=SizeOfMatrix;i++)
    for(int j=1;j<=i-1;j++)
     if(abs(M1[i][j])*abs(M1[j][i])>4)
      return true;
  }
 }
 return false;
}

bool nontrivial(){
 for(int i=1;i<=SizeOfMatrix; i++)
  if(Matrix[SizeOfMatrix+1][i]!=0)
   return true;
 return false; 
}

bool is_admissible(){
 int k;
 double e;
 k=1;       //compute e[SizeOfMatrix+1]                                  
 while((Matrix[k][SizeOfMatrix+1]==0)&&(k<=SizeOfMatrix))
  k++;
 if(k==SizeOfMatrix+1)
  return false;
 if((Matrix[k][SizeOfMatrix+1]*Matrix[SizeOfMatrix+1][k]<0)&&(Matrix[k][SizeOfMatrix+1]*Matrix[SizeOfMatrix+1][k]>=-4))
  e=-Matrix[SizeOfMatrix+1][k]/Matrix[k][SizeOfMatrix+1];
 else
  return false;
 for(k=1;k<=SizeOfMatrix;k++){
  if(Matrix[k][SizeOfMatrix+1]*Matrix[SizeOfMatrix+1][k]>=-4){
   if(Matrix[SizeOfMatrix+1][k]!=-e*Matrix[k][SizeOfMatrix+1])
    return false;
  }
 }
 return true;
}

bool valence2_is_admissible(){
 int Valence,Valence2,Valence4;
 Valence=0;Valence2=0;Valence4=0;
 for(int k=1;k<=SizeOfMatrix;k++){
  if((Matrix[k][SizeOfMatrix+1]!=0)){
   Valence++;
   if((abs(Matrix[k][SizeOfMatrix+1])==2)||(abs(Matrix[SizeOfMatrix+1][k])==2))
    Valence2++;
   if((abs(Matrix[k][SizeOfMatrix+1])==4)||(abs(Matrix[SizeOfMatrix+1][k])==4))
    Valence4++;
  }
 }
 if(((Valence2>0)&&(Valence>6))||((Valence2>1)&&(Valence>5))||((Valence2>2)&&(Valence>3))||((Valence4>0)&&(Valence>2)))
  return false;
 return true;
} 

void attach(int end_ ){ 
 int jmin,jmax;  
 if(end_==SizeOfMatrix){
  NumberOf2p=0;NumberOf3=0;NumberOf4p=0;NumberOf2m=0;NumberOf4m=0;
 }
 for(int i=-4;i<=4;i++){ 
// for(int i=-1;i<=1;i++){
  if(i==0){
   jmin=0;jmax=0;
  }
  if(i==1){
   jmin=-4;jmax=-1;
  }
  if(i==-1){
   jmin=1;jmax=4;
  }
  if(i==2){
   jmin=-2;jmax=-1;
  }
  if(i==-2){
   jmin=1;jmax=2;
  }
  if(abs(i)==3){
   jmin=3;jmax=3;
  }   
  if(abs(i)==4){
   jmin=-sgn(i);jmax=-sgn(i);
  }  
  for(int j=jmin;j<=jmax;j++){
//  for(int j=-1;j<=1;j++){
   if(abs(j)==3)
    NumberOf3++; 
   if((abs(i)*abs(j)==2)){
    if(sgn(i)==1) 
     NumberOf2p++;
    else NumberOf2m++;
   }
   if((abs(i)*abs(j)==4)){
    if(sgn(i)==1) 
     NumberOf4p++;
    else NumberOf4m++;
   }
//   f=fopen(NameOfOutput,"a");
//   fprintf(f,"\n n2=%d,n3=%d,n4=%d; ",NumberOf2,NumberOf3,NumberOf4); 
//   fclose(f); 
   if((NumberOf2m<3)&&(NumberOf2p<3)&&((NumberOf2p+NumberOf2m)<4)&&(NumberOf3<1)&&(NumberOf4m<2)&&(NumberOf4p<2)&&((NumberOf2p+NumberOf4p)<2)&&((NumberOf2m+NumberOf4m)<2)){
//    f=fopen(NameOfOutput,"a");
//    fprintf(f,"\n end_=%d,i=%d,j=%d; ",end_,i,j); 
//    fclose(f);
    Matrix[SizeOfMatrix+1][end_]=i;
    Matrix[end_][SizeOfMatrix+1]=j;
    if(end_>1)
     attach(end_-1);
    else{
     Matrix[SizeOfMatrix+1][SizeOfMatrix+1]=0;
     if((is_admissible())){
      if((valence2_is_admissible())){ 
       if((!nonmin_infinite())&&(nontrivial())){
        NumberOfAnswer++;
        print_last_line(Matrix);
        print_last_column(Matrix); 
       }
      }
     }
    }
   }
   if(abs(j)==3)
    NumberOf3--; 
   if((abs(i)*abs(j)==2)){
    if(sgn(i)==1) 
     NumberOf2p--;
    else NumberOf2m--;
   }
   if((abs(i)*abs(j)==4)){
    if(sgn(i)==1) 
     NumberOf4p--;
    else NumberOf4m--;
   }
//   if(abs(j)==3)
//    NumberOf3--; 
//   if(abs(i)*abs(j)==2)
//    NumberOf2--;
//   if(abs(i)*abs(j)==4)
//    NumberOf4--;
  }
 }
}

int main(){
 NumberOfRandomMutations=3000;
 printf("\n Print input filename:  ");
 scanf("%s", NameOfInput);
 file=fopen(NameOfInput,"r");
 printf("\n Print output filename:  ");
 scanf("%s", NameOfOutput);
 f=fopen(NameOfOutput,"w"); 
// file=fopen("E8_11.qmu","r");
// f=fopen("output_min.txt","w"); 
 fclose(f);
 NumberOfMatrix=0;
 while (!feof(file)){
  fgets(line,100,file);
  if(line[2]=='M'){  
   fscanf(file,"%d %d",&SizeOfMatrix, &SizeOfMatrix);
   for(int i=1;i<=SizeOfMatrix;i++)
    for(int j=1;j<=SizeOfMatrix;j++)
     fscanf(file,"%d ",&Matrix[i][j]);  
   NumberOfAnswer=0;
   NumberOfMatrix++;
   print_matrix();
   attach(SizeOfMatrix);
  }
 }
 fclose(file); 
 printf("Finished");
 return 0;
}