// min_inf.cpp

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

int SizeOfMatrix,NumberOfRandomMutations,NumberOfAnswer,Matrix[40][40],NumberOfMatrix, NumberOf2;
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   NewValencies=  " , 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);
}

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);
  for(int i=1;i<=NumberOfRandomMutations;i++){
   k=(rand() % (SizeOfMatrix))+1;
   mutation(M1,SizeOfMatrix,k);
   for(int i=1;i<=SizeOfMatrix;i++)
    for(int j=1;j<=SizeOfMatrix;j++)
     if(abs(M1[i][j])>2)
      return true;
  }
 }
 return false;
}

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

void attach(int end_ ){  
 if(end_==SizeOfMatrix)
  NumberOf2=0;
 for(int i=-2;i<=2;i++){
  if((i==2)||(i==-2))
   NumberOf2++;
  if(NumberOf2<2){
   Matrix[SizeOfMatrix+1][end_]=i;
   Matrix[end_][SizeOfMatrix+1]=-i;
   if(end_>1)
    attach(end_-1);
   else {
    Matrix[SizeOfMatrix+1][SizeOfMatrix+1]=0;
    if((!nonmin_infinite())&&(nontrivial())){
     NumberOfAnswer++;
     print_last_line(Matrix);
    }
   }
  }
  if((i==2)||(i==-2))
   NumberOf2--;
 }
}

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"); 
 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;
}