/* 
 * File:   makeDS.c
 * Author: kouno
 *
 * Created on 2008/07/12, 14:00
 * Version 2.0
 * Version 1 = makeSP
 */

#include <stdio.h>
#include <stdlib.h>
#define EXIT_FALSE 1
#define EXIT_ERROR 4
#define MAX_VERTEX_SIZE 15
#define MAX_EDGE_SIZE 2*MAX_VERTEX_SIZE
#define MAX_FACE_SIZE MAX_VERTEX_SIZE+1
#define MAX_TKK_SIZE 3*MAX_VERTEX_SIZE
#define MAX_SEARCH_SIZE 2*2*MAX_VERTEX_SIZE+1
#define MAX_LINE 1024
#define MAX_DATA 4096
#define MAX_SPRIT_DATA 100
int i,j,k,s,p,q,r;
FILE *fp1,*fp2,*fpout,*fpoutS;
char *infile1,*infile2;
char b1[MAX_LINE],b2[MAX_LINE];
int e[MAX_EDGE_SIZE][2];
int tkk[MAX_FACE_SIZE];
int edge[MAX_VERTEX_SIZE][4];
int houkouA[MAX_EDGE_SIZE];
int houkouZ[MAX_EDGE_SIZE];
int DE[MAX_FACE_SIZE][MAX_TKK_SIZE];
int DE1[MAX_FACE_SIZE][MAX_TKK_SIZE];
int UsedEdgeNum[MAX_EDGE_SIZE];
int UsedVertexHoukou[MAX_VERTEX_SIZE][4][4];
int First_Edge[MAX_FACE_SIZE];
int d_flag,e_flag;
// from checkDS.c ------------- from here  
int U[2][MAX_FACE_SIZE];
int Ori[2][MAX_FACE_SIZE];
int DSe[MAX_FACE_SIZE][3];
int te[2][MAX_FACE_SIZE][MAX_TKK_SIZE];
int tk[2][MAX_FACE_SIZE][MAX_TKK_SIZE];
int ts[2][MAX_FACE_SIZE][MAX_TKK_SIZE];
int searchD[MAX_SEARCH_SIZE][MAX_SEARCH_SIZE];
int searchOri[MAX_SEARCH_SIZE][MAX_SEARCH_SIZE];
int searchNum[MAX_SEARCH_SIZE][MAX_SEARCH_SIZE];
int NEe,NEk,NEs,PEe,PEk,PEs,tgte,tgtk,tgts;
int PEnum,NEnum;
int basee,basek,bases;
int pbasee,pbasek,pbases;
int firste,firstk,firsts;
int tmpe,tmpk,tmps;
int ae,ak,as,be,bk,bs;
int bad_flag=0;
int step;
int output_tkk;//set 1 in settkkdata(),set 0 in output()
int Dnum=0,Snum;
// from checkSP.c ------------- to here    
int  SPd_flag,SPe_flag,status;
int TargetDisk[MAX_FACE_SIZE];
int SourceDisk[MAX_FACE_SIZE];
int tgt_disk;
int SPFirst_Edge[MAX_FACE_SIZE];
int Orientation[MAX_FACE_SIZE];
int sigma[MAX_FACE_SIZE][MAX_EDGE_SIZE];
int sigmaInv[MAX_FACE_SIZE][MAX_EDGE_SIZE];
// from checkDS.c ------------- to here    
char DS[MAX_DATA][MAX_LINE];
// from checkDS.c ------------- from here  
// D[][] -> DE[][] e[][] ->DSe[][]
int splitoutNum=0;
int split_option=0;
char outfileS[MAX_LINE];

int egNum(int we,int wk,int ws){
  if(Ori[we][wk]==1){ return DE[wk][ws];}
  else{return -DE[wk][ws];}
}

int egNumg(int we,int wk,int ws){
  if(Ori[we][wk]==1){ return -DE[wk][ws];}
  else{return DE[wk][ws];}
}

int prev(int we,int wk,int ws){
  int wn;
  wn=ws-Ori[we][wk];
  if(wn<=0){wn=wn+tkk[wk];}
  if(wn>tkk[wk]){wn=wn-tkk[wk];}
  return wn;
}
int next(int we,int wk,int ws){
  int wn;
  wn=ws+Ori[we][wk];
  if(wn<=0){wn=wn+tkk[wk];}
  if(wn>tkk[wk]){wn=wn-tkk[wk];}
  return wn;
}
int prev_eg(int we,int wk,int ws){
  int wn;
  wn=prev(we,wk,ws);
  if(!tk[we][wk][wn]){return 0;}
  PEe=te[we][wk][wn];PEk=tk[we][wk][wn];
  PEs=prev(PEe,PEk,ts[we][wk][wn]);
  return 1;
}
int next_eg(int we,int wk,int ws){
  int wn;
  wn=next(we,wk,ws);
  if(!tk[we][wk][wn]){return 0;}
  NEe=te[we][wk][wn];NEk=tk[we][wk][wn];
  NEs=next(NEe,NEk,ts[we][wk][wn]);
  return 1;
}

int prev_tgt(int we,int wk,int ws){
  int wwe,wwk,wws;
  int b_flag=0;
  wwe=we;wwk=wk;wws=ws;
  PEnum=0;
  if(!prev_eg(wwe,wwk,wws)){
    PEe=wwe;PEk=wwk;PEs=wws;
    tgte=PEe;tgtk=PEk;tgts=PEs;
    b_flag=1;
  }else{
  while(prev_eg(wwe,wwk,wws)){
    if(PEe==we && PEk==wk && PEs==ws){b_flag=1;break;}
    wwe=PEe;wwk=PEk;wws=PEs;PEnum++;
  }
  }
  if(b_flag){return 0;}
  tgte=PEe;tgtk=PEk;tgts=PEs;
  return 1;
}

int next_tgt(int we,int wk,int ws){
  int wwe,wwk,wws;
  int b_flag=0;
  wwe=we;wwk=wk;wws=ws;
  NEnum=0;
  if(!next_eg(wwe,wwk,wws)){
    NEe=wwe;NEk=wwk;NEs=wws;
    tgte=NEe;tgtk=NEk;tgts=NEs;
    b_flag=1;
  }else{
  while(next_eg(wwe,wwk,wws)){
    if(NEe==we && NEk==wk && NEs==ws){b_flag=1;break;}
    wwe=NEe;wwk=NEk;wws=NEs;NEnum++;
  }
  }
  if(b_flag){return 0;}
  tgte=NEe;tgtk=NEk;tgts=NEs;
  return 1;
}

void set_default_data(void){
  int ep;
  for(ep=0;ep<=1;ep++){
    for(k=1;k<=r;k++){
      U[ep][k]=0;Ori[ep][k]=0;
      for(s=1;s<=tkk[k];s++){
	te[ep][k][s]=0;tk[ep][k][s]=0;ts[ep][k][s]=0;
      }
    }
  }
  for(i=0;i<=2*q;i++){
    for(j=0;j<=2*q;j++){
      searchD[i][i]=0;searchOri[i][j]=0;searchNum[i][j]=0;
    }
  }
  for(k=1;k<=r;k++){
    for(i=0;i<=2;i++){
      DSe[k][i]=0;
    }
  }
}

void set_search_data(void){
  for(k=1;k<=r;k++){
    for(s=1;s<tkk[k];s++){
      searchD[DE[k][s]+q][DE[k][s+1]+q]=k;
      searchD[-DE[k][s+1]+q][-DE[k][s]+q]=k;
      searchOri[DE[k][s]+q][DE[k][s+1]+q]=1;
      searchOri[-DE[k][s+1]+q][-DE[k][s]+q]=-1;
      searchNum[DE[k][s]+q][DE[k][s+1]+q]=s;
      searchNum[-DE[k][s+1]+q][-DE[k][s]+q]=s+1;
    }
      searchD[DE[k][tkk[k]]+q][DE[k][1]+q]=k;
      searchD[-DE[k][1]+q][-DE[k][tkk[k]]+q]=k;
      searchOri[DE[k][tkk[k]]+q][DE[k][1]+q]=1;
      searchOri[-DE[k][1]+q][-DE[k][tkk[k]]+q]=-1;
      searchNum[DE[k][tkk[k]]+q][DE[k][1]+q]=tkk[k];
      searchNum[-DE[k][1]+q][-DE[k][tkk[k]]+q]=1;
  }
}

void loop_check(void){
  int a;
  int ret1,ret;
  bad_flag=0;
  while(1){
    if(egNum(basee,basek,bases)!=egNumg(pbasee,pbasek,pbases)){bad_flag=1;break;}
    ret1=prev_eg(pbasee,pbasek,pbases);
    ret=next_eg(basee,basek,bases);
    if(ret1==1 && ret==1){bad_flag=1;break;}
    if(ret1==0 && ret==0){
      te[basee][basek][bases]=pbasee;
      tk[basee][basek][bases]=pbasek;
      ts[basee][basek][bases]=pbases;
      te[pbasee][pbasek][pbases]=basee;
      tk[pbasee][pbasek][pbases]=basek;
      ts[pbasee][pbasek][pbases]=bases;
      bases=next(basee,basek,bases);
      break;
    }      
    if(ret1==1){
      pbasee=PEe;pbasek=PEk;pbases=PEs;
      bases=next(basee,basek,bases);
    }
    if(ret==1){
      pbases=prev(pbasee,pbasek,pbases);
      basee=NEe;basek=NEk;bases=NEs;
    }
  }
}

void nextks(void){
  if(s<tkk[k]){s++;}
  else{k++;s=1;}
}

int check_base(void){
  int wOri;
  ae=basee;ak=basek;as=bases;
  if(!prev_eg(ae,ak,as)){printf ("ERROR! [check_base] [%d,%d,%d]\n",ae,ak,as);return 1;}
  be=PEe;bk=PEk;bs=PEs;
  k=searchD[q+egNum(be,bk,bs)][q+egNum(ae,ak,as)];
  if(k==0){return -1;}
  wOri=searchOri[q+egNum(be,bk,bs)][q+egNum(ae,ak,as)];
  if(Ori[0][k]==0){
    U[0][k]=1;Ori[0][k]=-wOri;Ori[1][k]=wOri;
    DSe[k][1-wOri]=0;DSe[k][1+wOri]=1;
    tmpe=0;tmpk=k;
    return 1;
  }
  if(Ori[0][k]==-wOri && U[0][k]==0){
    U[0][k]=1;
    tmpe=0;tmpk=k;
    return 1;}
  if(Ori[1][k]==-wOri && U[1][k]==0){
    U[1][k]=1;
    tmpe=1;tmpk=k;
    return 1;}
  return 0;
}

int next_base(void){
  int a,ret;
  bad_flag=0;
  ret=check_base();
  if(ret==-1){return -1;}
  if(ret==1){return 1;}
  if(prev_tgt(basee,basek,bases)==0){return 0;}
  firste=PEe;firstk=PEk;firsts=PEs;
  while(!ret){
    if(next_tgt(basee,basek,bases)){
    ae=tgte;ak=tgtk;as=tgts;
    }else{
    ae=basee;ak=basek;as=bases;
    }
    while(!next_eg(ae,ak,as)){as=next(ae,ak,as);}
    if(firste==ae && firstk==ak && firsts==as){bad_flag=1;break;}
    next_eg(ae,ak,as);
    basee=NEe;basek=NEk;bases=NEs;
    ret=check_base();
    if(ret==-1){bad_flag=-1;break;}
    if(ret==1){break;}
  }
  if(bad_flag==1){return 0;}
  return 1;
}

int check_DS_data(void){
  int a,EL;
  int found_flag=0;
  // first
  U[0][1]=1;Ori[0][1]=1;Ori[1][1]=-1;
  DSe[1][1+1]=0;DSe[1][1-1]=1;
  a=egNum(0,1,1);
  for(s=2;s<=tkk[1];s++){
    if(a==DE[1][s]){
      U[1][1]=1;
      te[0][1][1]=1;tk[0][1][1]=1;ts[0][1][1]=s;
      te[1][1][s]=0;tk[1][1][s]=1;ts[1][1][s]=1;
      found_flag=1;break;
    }
  }
    if(found_flag==0){
      for(k=2,s=1;k<=r;nextks()){
	  if(a==DE[k][s]){
	    U[0][k]=1;Ori[0][k]=-1;Ori[1][k]=1;
	    DSe[k][1-1]=0;DSe[k][1+1]=1;
	    te[0][1][1]=0;tk[0][1][1]=k;ts[0][1][1]=s;
	    te[0][k][s]=0;tk[0][k][s]=1;ts[0][k][s]=1;
	    found_flag=1;break;
	  }
	  if(a==-DE[k][s]){
	    U[0][k]=1;Ori[0][k]=1;Ori[1][k]=-1;
	    DSe[k][1+1]=0;DSe[k][1-1]=1;
	    te[0][1][1]=0;tk[0][1][1]=k;ts[0][1][1]=s;
	    te[0][k][s]=0;tk[0][k][s]=1;ts[0][k][s]=1;
	    found_flag=1;break;
	  }
      }
    }
    if(found_flag==0){return 0;}
    step=3;basee=0;basek=1;bases=2;
  // loop
    while(step<2*r){
      if(next_base()==0){ return 0;}
      next_tgt(basee,basek,bases);
      prev_tgt(basee,basek,bases);
      EL=PEnum+NEnum+1;
      if(tkk[tmpk]<EL){bad_flag=1;break;}
      ae=tgte;ak=tgtk;as=tgts;
      next_eg(ae,ak,as);be=NEe;bk=NEk;bs=NEs;
      if(tmpk!=searchD[q+egNum(ae,ak,as)][q+egNum(be,bk,bs)] 
	 || Ori[tmpe][tmpk]!=-searchOri[q+egNum(ae,ak,as)][q+egNum(be,bk,bs)])
	{bad_flag=1;break;}
      tmps=searchNum[q+egNum(ae,ak,as)][q+egNum(be,bk,bs)];
      te[ae][ak][as]=tmpe;tk[ae][ak][as]=tmpk;ts[ae][ak][as]=tmps;
      te[tmpe][tmpk][tmps]=ae;tk[tmpe][tmpk][tmps]=ak;ts[tmpe][tmpk][tmps]=as;
      if(egNum(ae,ak,as)!=egNumg(tmpe,tmpk,tmps)){bad_flag=1;break;}
      for(j=2;j<=EL;j++){
	tmps=prev(tmpe,tmpk,tmps);
	next_eg(ae,ak,as);ae=NEe;ak=NEk;as=NEs;
	if(egNum(ae,ak,as)!=egNumg(tmpe,tmpk,tmps)){bad_flag=1;break;}
      }
      if(bad_flag==1){break;}
      te[ae][ak][as]=tmpe;tk[ae][ak][as]=tmpk;ts[ae][ak][as]=tmps;
      te[tmpe][tmpk][tmps]=ae;tk[tmpe][tmpk][tmps]=ak;ts[tmpe][tmpk][tmps]=as;
      // set only ends
      bs=next(ae,ak,as);basee=ae;basek=ak;bases=bs;
      bs=prev(tgte,tgtk,tgts);pbasee=tgte;pbasek=tgtk;pbases=bs;
      step++;
      if(EL==tkk[tmpk]){loop_check();}
      if(bad_flag==1){break;}
    }
    if(bad_flag==1){return 0;}
  // last check
    if(prev_tgt(basee,basek,bases)==1){return 0;}
    next_eg(basee,basek,bases);
    bk=searchD[q+egNum(basee,basek,bases)][q+egNum(NEe,NEk,NEs)];
    be=searchOri[q+egNum(basee,basek,bases)][q+egNum(NEe,NEk,NEs)];
    be=DSe[bk][1-be];
    if(U[be][bk]==1){return 0;}
    bs=searchNum[q+egNum(basee,basek,bases)][q+egNum(NEe,NEk,NEs)];
    ae=basee;ak=basek;as=bases;
    for(j=1;j<=tkk[bk];j++){
      if(egNum(ae,ak,as)!=egNumg(be,bk,bs)){return 0;}
      next_eg(ae,ak,as);ae=NEe;ak=NEk;as=NEs;
      bs=prev(be,bk,bs);
    }
    return 1;
}

// from checkDS.c ------------- to here    

int dlength(int n){
  if(n<=-100) return 4;
  if(n<=-10) return 3;
  if(n<0) return 2;
  if(n<10) return 1;
  if(n<100) return 2;
  return 3;
}

int abs(int n){
  if(n>=0){return n;}
  else{return -n;}
}
int HoukouA(int wk,int wl){
    if(DE[wk][wl]>0){return houkouA[abs(DE[wk][wl])];}
    else{return houkouZ[abs(DE[wk][wl])];}
}
int HoukouZ(int wk,int wl){
    if(DE[wk][wl]>0){return houkouZ[abs(DE[wk][wl])];}
    else{return houkouA[abs(DE[wk][wl])];}
}
int VertexA(int wk,int wl){
    if(DE[wk][wl]>0){return e[abs(DE[wk][wl])][0];}
    else{return e[abs(DE[wk][wl])][1];}
}
int VertexZ(int wk,int wl){
    if(DE[wk][wl]>0){return e[abs(DE[wk][wl])][1];}
    else{return e[abs(DE[wk][wl])][0];}
}
int output(void){
  int wk,wl;
    char *bb;
    // checkDS  ------------- from here
    bb=b1;
    for(k=1,s=1;k<=r;nextks()){
      sprintf(bb,"%d,",DE[k][s]);bb=bb+1+dlength(DE[k][s]);
    }
    strcpy(DS[Dnum],b1);
    Dnum++;
    // checkDS  ------------- to here
    if(output_tkk){
    fprintf(fpout,"##");printf("##");
    for(wk=1;wk<r;wk++){fprintf(fpout,"%d,",tkk[wk]);printf("%d,",tkk[wk]);}
    fprintf(fpout,"%d\n",tkk[r]);printf("%d\n",tkk[r]);
    //splitout
    if(split_option){
    fprintf(fpoutS,"##");
    for(wk=1;wk<r;wk++){fprintf(fpoutS,"%d,",tkk[wk]);}
    fprintf(fpoutS,"%d\n",tkk[r]);
    }
    }
    output_tkk=0;
    for(wk=1;wk<=r;wk++){ fprintf(fpout,"* ");printf("* ");
        for(wl=1;wl<=tkk[wk];wl++){
            fprintf(fpout,"%d ",DE[wk][wl]);
            printf("%d ",DE[wk][wl]);}
    }
    fprintf(fpout,"\n");printf("\n");
    //splitout
    if(split_option){
    for(wk=1;wk<=r;wk++){ fprintf(fpoutS,"* ");
        for(wl=1;wl<=tkk[wk];wl++){
            fprintf(fpoutS,"%d ",DE[wk][wl]);
        }
    }
    fprintf(fpoutS,"\n");
    splitoutNum++;
    if(splitoutNum>=MAX_SPRIT_DATA){
      close(fpoutS);
    if(NULL==(fpoutS=fopen(outfileS,"a"))){
    printf("Cannot open file %s\n",outfileS);
    return(EXIT_FALSE);}
    splitoutNum=0;}
    }
}

int check_last(void){
    if(VertexA(k,1)!=VertexZ(k,tkk[k])){return EXIT_FALSE;}
    if(HoukouA(k,1)==HoukouZ(k,tkk[k])){return EXIT_FALSE;}
    if(UsedVertexHoukou[VertexA(k,1)][HoukouA(k,1)][HoukouZ(k,tkk[k])]==1){return EXIT_FALSE;}
    UsedVertexHoukou[VertexA(k,1)][HoukouZ(k,tkk[k])][HoukouA(k,1)]=1;
    UsedVertexHoukou[VertexA(k,1)][HoukouA(k,1)][HoukouZ(k,tkk[k])]=1;
    // check self-contact
    return EXIT_SUCCESS;
}
int setS1data(){
    int wi,wj,wn,w1,w2,h1,h2,i1,i2;
    int t_houkou[MAX_VERTEX_SIZE];
    char *bb;
    Dnum=0;
    wn=fgets(b1,MAX_LINE,fp1);
    if(wn==0){return(0);}    
    while(b1[0]=='#'){wn=fgets(b1,MAX_LINE,fp1);}
    if(wn==0) return 0;
    fprintf(fpout,"#%s",b1);
    printf("#%s",b1);
    wj=0;bb=b1;
    //printf("#");
    while(sscanf(bb,"(%d,%d)",&w1,&w2)){wj++;
        e[wj][0]=w1;e[wj][1]=w2;
        bb=bb+4+dlength(w1)+dlength(w2);
	//printf("(%d,%d)",w1,w2);
    }
    //printf("\n");
    q=wj;p=wj/2;r=p+1;
    for(wi=1;wi<=p;++wi){t_houkou[wi]=0;}
    for(wj=1;wj<=q;++wj){i1=e[wj][0];i2=e[wj][1];
        h1=t_houkou[i1];t_houkou[i1]++;
        h2=t_houkou[i2];t_houkou[i2]++;
        //vertex[i1][h1]=i2;vertex[i2][h2]=i1;
        edge[i1][h1]=wj;edge[i2][h2]=wj;
	//houkou[i1][h1]=h2;houkou[i2][h2]=h1;
        houkouA[wj]=h1;houkouZ[wj]=h2;
    }
    return(1);
    
}
int settkkdata(){
    int wi,wn,n1;
    char *bb;
    Dnum=0;
    wn=fgets(b2,MAX_LINE,fp2);
    if(wn==0){return(0);}    
    while(b2[0]=='#'){wn=fgets(b2,MAX_LINE,fp2);}
    if(wn==0) return(0);    
    //fprintf(fpout,"##%s",b2);
    //printf("##");
    wi=0;bb=b2;
    sscanf(bb,"%d",&n1);wi++;tkk[wi]=n1;
    bb=bb+dlength(n1);
    //printf("%d ",n1);
    while(sscanf(bb,",%d",&n1)){wi++;
    tkk[wi]=n1;
    bb=bb+1+dlength(n1);
    //printf("%d ",n1);
    }
    //printf("\n");
    //r=wi;
    output_tkk=1;
    return(1);
}

int self_contact(int wh){
  int ws,e1,v1,flag;
  flag=1;
  v1=VertexZ(k,s-1);e1=edge[v1][wh];
  if(e[e1][0]==e[e1][1]){
    //v1=v2
    if(wh==houkouA[e1]){DE[k][s]=e1;
    }else{DE[k][s]=-1*e1;}
  }else{
    //v1!=v2
    if(v1==e[e1][0]){DE[k][s]=e1;
    }else{DE[k][s]=-1*e1;}
  }
  for(ws=1;ws<s;ws++){
    if(DE[k][ws]==-1*DE[k][s]){flag=0;break;}
  }
  return flag;
}

void setedge(void){
  int wj,wh,ws,h1,v1,e1;
  int First_Houkou;
  if(s==1){
    if(e_flag==1){
      if(tkk[k-1]==tkk[k]){First_Edge[k]=DE[k-1][1];
      }else{First_Edge[k]=1;}
    }else{
      First_Edge[k]=DE[k][1]+1;
    }
    //s=1
    if(e_flag==-1){UsedEdgeNum[DE[k][1]]--;}
    for(wj=First_Edge[k];wj<=q;wj++){if(UsedEdgeNum[wj]<3) break;}
    if(wj==q+1){
      //FALSE
      e_flag=-1;s--;
    }else{
      //SUCCESS
      DE[k][s]=wj;
      First_Edge[k]=wj;
      UsedEdgeNum[wj]++;
      e_flag=1;s++;
    }
  }else{
    //s>1
    if(e_flag==-1){
      UsedEdgeNum[abs(DE[k][s])]--;
      UsedVertexHoukou[VertexA(k,s)][HoukouA(k,s)][HoukouZ(k,s-1)]=0;
      UsedVertexHoukou[VertexA(k,s)][HoukouZ(k,s-1)][HoukouA(k,s)]=0;
    }
    if(e_flag==1){First_Houkou=0;}
    else{First_Houkou=HoukouA(k,s)+1;}
    h1=HoukouZ(k,s-1);v1=VertexZ(k,s-1);
    for(wh=First_Houkou;wh<4;wh++){e1=edge[v1][wh];
      if(wh!=h1 && UsedVertexHoukou[v1][h1][wh]==0
	 && e1>=First_Edge[k] && UsedEdgeNum[e1]<3
	 && self_contact(wh)) break;
    }
    if(wh==4){
      //FALSE
      e_flag=-1;s--;
    }else{
      //SUCCESS
	if(e[e1][0]==e[e1][1]){
	  //v1=v2
	  if(wh==houkouA[e1]){DE[k][s]=e1;
	  }else{DE[k][s]=-1*e1;}
	}else{
	  //v1!=v2
	  if(v1==e[e1][0]){DE[k][s]=e1;
	  }else{DE[k][s]=-1*e1;}
	}
	UsedVertexHoukou[v1][h1][wh]=1;
	UsedVertexHoukou[v1][wh][h1]=1;
	UsedEdgeNum[e1]++;
	e_flag=1;s++;
    }
  }
}
void delete_disk_data(void){
    int ws;
    for(ws=1;ws<tkk[k];ws++){
        UsedEdgeNum[abs(DE[k][ws])]--;
        UsedVertexHoukou[VertexZ(k,ws)][HoukouZ(k,ws)][HoukouA(k,ws+1)]=0;
        UsedVertexHoukou[VertexZ(k,ws)][HoukouA(k,ws+1)][HoukouZ(k,ws)]=0;
    }
    UsedEdgeNum[abs(DE[k][tkk[k]])]--;
    UsedVertexHoukou[VertexA(k,1)][HoukouZ(k,ws)][HoukouA(k,1)]=0;
    UsedVertexHoukou[VertexA(k,1)][HoukouA(k,1)][HoukouZ(k,ws)]=0;
}
void delete_all_data(void){
  int wi,wj,wk,ws;
  for(wk=1;wk<=r;wk++){
      for(ws=1;ws<=tkk[k];ws++){
        DE[wk][ws]=0;
      }
  }
  for(wj=1;wj<=q;wj++){
    UsedEdgeNum[wj]=0;
	 }
  for(wi=1;wi<=p;wi++){
    UsedVertexHoukou[wi][0][1]=0;UsedVertexHoukou[wi][0][2]=0;
    UsedVertexHoukou[wi][0][3]=0;
    UsedVertexHoukou[wi][1][0]=0;UsedVertexHoukou[wi][1][2]=0;
    UsedVertexHoukou[wi][1][3]=0;
    UsedVertexHoukou[wi][2][0]=0;UsedVertexHoukou[wi][2][1]=0;
    UsedVertexHoukou[wi][2][3]=0;
    UsedVertexHoukou[wi][3][0]=0;UsedVertexHoukou[wi][3][1]=0;
    UsedVertexHoukou[wi][3][2]=0;
	 }
}

void setdisk(void){
  if(d_flag==-1){s=tkk[k];}else{s=1;}
  while(0<s && s<=tkk[k]){
    setedge();
  if(s==tkk[k]+1){if(check_last()){s--;e_flag=-1;}}
  }
  if(s==0){
    k--;d_flag=-1;e_flag=-1;
    UsedVertexHoukou[VertexA(k,1)][HoukouZ(k,tkk[k])][HoukouA(k,1)]=0;
    UsedVertexHoukou[VertexA(k,1)][HoukouA(k,1)][HoukouZ(k,tkk[k])]=0;}
  if(s==tkk[k]+1){k++;d_flag=1;e_flag=1;}
}

// from checkSP.c ------------- from here    
  // First_Edge[] ->SPFirst_Edge[]
  // d_flag -> SPd_flag e_flag -> SPe_flag
  // DiskEdge[][] => DE[][] DiskEdgeT[][] -> DE1[][]
int sgn(int n){
  if(n>0) return 1;
  else if(n==0) return 0;
  else
    return -1;
}

int tau(int ws){
  int wret;
  wret=SPFirst_Edge[k]+Orientation[k]*(ws-1);
  if(tkk[k]<wret){wret=wret-tkk[k];}
  if(wret<=0){wret=wret+tkk[k];}
  return wret;
}

int Sigma(int wj){
   if (wj>0){return sigma[k][wj];
   }else{return -1*sigma[k][-1*wj];}
 }

int SigmaInv(int wj){
   if (wj>0){return sigmaInv[k][wj];
   }else{return -1*sigmaInv[k][-1*wj];}
 }

int check_sigma(void){
  int ws,wj;
  for(wj=1;wj<=q;wj++){
    sigma[k][wj]=sigma[k+1][wj];sigmaInv[k][wj]=sigmaInv[k+1][wj];
  }
  for(ws=1;ws<=tkk[k];ws++){
    if(Sigma(DE[k][ws])){
      if(Sigma(DE[k][ws])!=DE1[TargetDisk[k]][tau(ws)]*Orientation[k]) break;
      if(SigmaInv(DE1[TargetDisk[k]][tau(ws)]*Orientation[k])!=DE[k][ws]) break;
    }else{
      if(SigmaInv(DE1[TargetDisk[k]][tau(ws)])*Orientation[k]) break;
      sigma[k][abs(DE[k][ws])]=DE1[TargetDisk[k]][tau(ws)]*Orientation[k]*sgn(DE[k][ws]);
      sigmaInv[k][abs(DE1[TargetDisk[k]][tau(ws)])]
	=DE[k][ws]*Orientation[k]*sgn(DE1[TargetDisk[k]][tau(ws)]);
    }
  }
  //printf("check_sigma First[%d] Ori[%d]\n",SPFirst_Edge[k],Orientation[k]);//debug
  if(ws==tkk[k]+1){return EXIT_SUCCESS;}
  else{return EXIT_FALSE;}
}

void first_edge_next(void){
  if(Orientation[k]==1){
    if(SPFirst_Edge[k]<tkk[k]){SPFirst_Edge[k]++;}else{Orientation[k]=-1;}
  }else{
      SPFirst_Edge[k]--;
  }
}

int search_tgt_disk(void){
  int wk,kmin,kmax;
  for(wk=k-1;tkk[k]==tkk[wk];wk--){}kmin=wk+1;
  if(SPd_flag==0){kmax=--TargetDisk[k];
  if(tkk[kmax]!=tkk[k]){return EXIT_FALSE;}
  }else{
    for(wk=k+1;tkk[k]==tkk[wk];wk++){}kmax=wk-1;
  }
  for(wk=kmax;kmin<=wk;wk--){if(SourceDisk[wk]==0) break;}
  if(wk<kmin){
    return EXIT_FALSE;
  }else{
    tgt_disk=wk;
    return EXIT_SUCCESS;
  }
}

void check_Disk(void){
  int ws;
  //printf("chec_Disk k[%d] status[%d] Target[%d] Ori[%d]\n",k,status,TargetDisk[k],Orientation[k]);//debug
  switch(status){
  case 0: // search tgt disk
    if(SPd_flag==0){SourceDisk[TargetDisk[k]]=0;}
    if(SPd_flag==-1){
      SPe_flag=-1;status=1;
    }else if(search_tgt_disk()){
      TargetDisk[k]=0; SourceDisk[TargetDisk[k]]=0;
      k++;SPd_flag=-1;
    }else{
      TargetDisk[k]=tgt_disk;SourceDisk[tgt_disk]=k;
      status=1;SPe_flag=1;
    }
    break;
  case 1: // check tgt disk
    if(SPe_flag==1){
      SPFirst_Edge[k]=1;Orientation[k]=1;
    }else{
      first_edge_next();
    }
    for(;0<SPFirst_Edge[k];first_edge_next()){
      if(!check_sigma()){break;}
    }
    if(SPFirst_Edge[k]==0){
      SPd_flag=0;status=0;SPe_flag=-1;
    }else{
      SPd_flag=1;SPe_flag=1;status=0;k--;
    }
    break;
  }
}

int check_Disk_data(void){
  int wk;
  for(wk=1;wk<=r;wk++){TargetDisk[wk]=0;SourceDisk[wk]=0;}
  //  for(wk=1;wk<=r;wk++){TargetDisk[wk]=0;SourceDisk[wk]=0;Orientation[wk]=0;}
  SPd_flag=1; status=0; k=r;
  while(0<k&& k<=r){check_Disk();}
  if(k==0){return 1;}else{return 0;}
}

// from checkSP.c ------------- to here    

void getDSdata(int wi){
  int n1;
  char *bb;
  //printf("getDSdata[%d] ",wi);//debug
  bb=DS[wi];
  for(k=1,s=1;k<=r;nextks()){
    sscanf(bb,"%d",&n1);DE1[k][s]=n1;
    bb=bb+1+dlength(n1);
    //printf("%d ",DE1[k][s]);//debug
  }
  //printf("\n");//debug
}

int check_same(int wi){
  getDSdata(wi);
  //if(check_Disk_data()){return 0;}else{return 1;}
  if(check_Disk_data()){return 1;}else{return 0;}
}

int check_outdata(void){
  int wi;
  int same_flag=1;
  for(wi=0;wi<Dnum;wi++){
    if(check_same(wi)){same_flag=0;break;}
  }
  return same_flag;
}

int isolated(void){
  int iso_flag;
  int DB[MAX_EDGE_SIZE];
  for(k=1;k<=r;k++){
    for(j=1;j<=q;j++){DB[j]=0;}
    for(s=1;s<=tkk[k];s++){
      DB[abs(DE[k][s])]++;
      if(DB[abs(DE[k][s])]>=2){iso_flag=0;break;}
    }
    if(!iso_flag){break;}
  }
  return iso_flag;
}

int main(int argc, char** argv) {
    int ret,wk,wj;
    int ai=1;
    char *outfile;
    int isolated_option=0;
    int nonisolated_option=0;
    if(argc<=2){
      printf("Usage: %s [-splitout/isolated] S1DataFile tkkDataFile [DSfile(default is DSData)]\n",argv[0]);
      return EXIT_FALSE;
    }
    //for(wk=1;wk<=r;wk++){FirstEdge[tkk[wk]]=1;}
    if(!strcmp(argv[ai],"-splitout")){split_option=1;ai++;}
    if(!strcmp(argv[ai],"-isolated")){isolated_option=1;ai++;}
    if(!strcmp(argv[ai],"-nonisolated")){nonisolated_option=1;ai++;}
    infile1=argv[ai];ai++;infile2=argv[ai];ai++;
    if(argv[ai]){outfile=argv[ai];
    }else{outfile="DSData";}
    sprintf(outfileS,"%s-split",outfile);
    if(NULL==(fp1=fopen(infile1,"r"))){
    printf("Cannot open file %s\n",infile1);
    return(EXIT_FALSE);}
    if(NULL==(fpout=fopen(outfile,"a"))){
    printf("Cannot open file %s\n",outfile);
    return(EXIT_FALSE);}
    if(split_option){
    if(NULL==(fpoutS=fopen(outfileS,"w"))){
    printf("Cannot open file %s\n",outfileS);
    return(EXIT_FALSE);}
    }
    //fprintf(fpout,"# S1file[%s] tkkfile[%s]\n",infile1,infile2);
    //if(split_option){fprintf(fpoutS,"# S1file[%s] tkkfile[%s]\n",infile1,infile2);}
   while(setS1data()){
       if(NULL==(fp2=fopen(infile2,"r"))){
       printf("Cannot open file %s\n",infile2);
       return(EXIT_FALSE);}
       while(settkkdata()){
	 delete_all_data();
	 k=1;d_flag=1;e_flag=1;
	 while(0<k){
	   setdisk();
	   if(k==r+1){set_default_data();set_search_data();
	     if(check_DS_data() && check_outdata()){
	       if(isolated_option){
		 if(isolated()){output();}
	       }else if(nonisolated_option){
		 if(!isolated()){output();}
	       }else{
		 output();}
	     } 
	     k=r;d_flag=-1;e_flag=-1;
	     UsedVertexHoukou[VertexA(k,1)][HoukouZ(k,tkk[k])][HoukouA(k,1)]=0;
	     UsedVertexHoukou[VertexA(k,1)][HoukouA(k,1)][HoukouZ(k,tkk[k])]=0;}
	 }
       }
   }
    return (EXIT_SUCCESS);
}