/* 
 * File:   makeS1.c
 * Author: kouno
 *
 * Created on 2008/04/23, 20:19
 * Version 2.0
 */

#define KNOOUT 1

#include <stdio.h>
#include <stdlib.h>

#define EXIT_FALSE 1
#define MAX_VERTEX_SIZE 15
#define MAX_EDGE_SIZE 2*MAX_VERTEX_SIZE
#define MAX_LINE 2048
int i,j,p,q;
int num=0;
int e[MAX_EDGE_SIZE][2];
int UsedVertexNum[MAX_VERTEX_SIZE];
int g[MAX_VERTEX_SIZE];
char *out;

void output(void){
    int wj;
    FILE *fp;
    //    if(NULL==(fp=fopen(OUT_FILE,"a"))){
    //if(NULL==(fp=fopen(OUT_FILE,"a"))){
    if(NULL==(fp=fopen(out,"a"))){
        printf("Cannot open file \n");
        return(EXIT_FALSE);
    }
    for(wj=1;wj<q;++wj){
        fprintf(fp,"(%d,%d),",e[wj][0],e[wj][1]);
#if KNOOUT
        printf("(%d,%d),",e[wj][0],e[wj][1]);
#endif
    }
    num++;
    fprintf(fp,"(%d,%d)# %d\n",e[q][0],e[q][1],num);
#if KNOOUT
    printf("(%d,%d)# %d\n",e[q][0],e[q][1],num);
#endif
    fclose(fp);
}

void write_data_file(void){
    FILE *fp;
    //if(NULL==(fp=fopen(OUT_FILE,"a"))){
    if(NULL==(fp=fopen(out,"a"))){
        printf("Cannot open file \n");
        return(EXIT_FALSE);
    }
    fprintf(fp,"# p=%d\n",p);
#if KNOOUT
    printf("# p=%d\n",p);
#endif
    fclose(fp);
}

int check_double_loop(void){
    int wj,wj1,wj2;
    for(wj=1;wj<q;wj++){
        if(e[wj][0]==e[wj][1]){
            wj1=wj+1;
            while(e[wj1][0]==e[wj][0]){
                wj2=wj+1;
                while(e[wj2][0]<=e[wj1][1]){
                    if(e[wj2][0]==e[wj2][1]&&e[wj1][1]==e[wj2][0]) return(EXIT_SUCCESS);
                    wj2++;
                }
                wj1++;
            }
        }
    }
    return(EXIT_FALSE);
}
int check_triple_edge(viod){
    int wj,flag;
    for(wj=1;wj<=q;++wj){
        if(e[wj-1][0]==e[wj][0]&&e[wj-1][1]==e[wj][1]){
            if(flag==1) return(EXIT_SUCCESS);
            flag++;
        }else{
            flag=0;
        }
    }
    return(EXIT_FALSE);
}
int check_cutvertex(void){
    int wi,wj,maxi;
    for(wi=1;wi<=p;wi++){
        if(wi==1){maxi=2;}else{maxi=1;}
        for(wj=1;wj<=q;wj++){
            if(e[wj][0]==wi||e[wj][1]==wi){}else{
                if(e[wj][0]>maxi){return(EXIT_SUCCESS);}
                maxi=(e[wj][1] > maxi) ? e[wj][1] : maxi ;
            }
        }
    }
    return(EXIT_FALSE);
 }
int addpoint(int j1,int j2){
  int wj;
  int flag=0;
  for(wj=1;wj<=q;wj++){
    if(wj!=j1 && wj!=j2 && ((g[e[wj][0]]==0 && g[e[wj][1]]==1)||
			    (g[e[wj][0]]==1 && g[e[wj][1]]==0))){
      g[e[wj][0]]=1;g[e[wj][1]]=1;flag=1;break;
    }
  }
  return(flag);
}
int check_separate(void){
  int j1,j2,wi;
  int flag=1;
  for(j1=1;j1<=q-1;j1++){
    for(j2=j1+1;j2<=q;j2++){
      g[1]=1;for(wi=2;wi<=p;wi++){g[wi]=0;}
      while(addpoint(j1,j2)){}
      for(wi=1;wi<=p;wi++){if(g[wi]==0){flag=0;break;}}
    }
    if(!flag){break;}
  }
  return(flag);
}

int check_loop(void){
  int ret=1;
  int wj;
  for(wj=1;wj<=q;wj++){
    if(e[wj][0]==e[wj][1]){ret=0;break;}
  }
  return(ret);
}

int search_next_vertex(int wi){
    while(UsedVertexNum[wi]==4){wi++;}
    return(wi);
    }
int set(void){
    int wi;//,wa;
    if(UsedVertexNum[i]==0){
        j--;i=e[j][0];
	// UsedVertexNum[i]--;UsedVertexNum[e[j][1]]--;
        return(EXIT_FALSE);
    }
    if(e[j-1][0]==i){
        UsedVertexNum[i]++;
        wi=search_next_vertex(e[j-1][1]);
        if(wi>p){
            UsedVertexNum[i]--;j--;i=e[j][0];
	    //UsedVertexNum[i]--;UsedVertexNum[e[j][1]]--;
            return(EXIT_FALSE);
        }
        e[j][0]=i;e[j][1]=wi;
        UsedVertexNum[wi]++;
        i=search_next_vertex(i);j++;
        return(EXIT_SUCCESS);
    }
    UsedVertexNum[i]++;
    wi=search_next_vertex(i);
        if(wi>p){
            UsedVertexNum[i]--;j--;i=e[j][0];
	    //UsedVertexNum[i]--;UsedVertexNum[e[j][1]]--;
            return(EXIT_FALSE);
        }
    e[j][0]=i;e[j][1]=wi;
    UsedVertexNum[wi]++;
    j++;i=search_next_vertex(i);            
        return(EXIT_SUCCESS);
    
}
int reset(void){
    int wi;
    wi=e[j][1];
    if(UsedVertexNum[wi]==1){
        UsedVertexNum[i]--;UsedVertexNum[wi]--;
        j--; i=e[j][0];
        return(EXIT_FALSE);
    }
    // UsedVertexNum[wi]--;
    wi++; wi=search_next_vertex(wi);
    if(wi>p){
        UsedVertexNum[e[j][0]]--;
      	UsedVertexNum[e[j][1]]--;
        j--; i=e[j][0];
        return(EXIT_FALSE); 
    }
    UsedVertexNum[e[j][1]]--;
    UsedVertexNum[wi]++;
    e[j][0]=i;e[j][1]=wi;j++;
    i=search_next_vertex(i);
    return(EXIT_SUCCESS);
}
int main(int argc, char** argv) {
  int ret,ret1,ai=1;
  int loop_option=0;
  int separate_option=0;
  if(argc==1){
    printf("Usage: %s [-loop/-separate] VertexNumber [S1file(default S1Data)]\n",argv[0]);
    return EXIT_FALSE;
    }
  if(!strcmp(argv[ai], "-loop")){loop_option=1;separate_option=1;ai++;}
  if(!strcmp(argv[ai], "-separate")){separate_option=1;ai++;}
  if(!strcmp(argv[ai], "-loop")){loop_option=1;separate_option=1;ai++;}
  p=atoi(argv[ai]);
    q=p*2;
    if(argv[ai+1]){out=argv[ai+1];}else{out="S1Data";}
    write_data_file();

    i=1;j=1;
    e[1][0]=1;e[1][1]=1;
    UsedVertexNum[1]=2;j=2;
    while(j>0){
        while(j<=q){
        ret=set();
        if(ret==EXIT_FALSE) break;
        }
        if(j==q+1){
            if(check_double_loop()&&check_triple_edge()){
	      ret=check_loop();
	      if(loop_option){ret=1;}
	      ret1=check_separate();
	      if(separate_option){ret1=1;}
	      if(ret==1 && ret1==1)output();
            }
            j--;i=e[j][0];
        }
        while(j>0){
            ret=reset();
            if(ret==EXIT_SUCCESS) break;
        }
    }
    //printf("Number=[%d]\n",p);
    return (EXIT_SUCCESS);
}