/*Finds rotations for an instance of stable marriage
  based on Gale-Shapley lists*/
/*BP Weems 3/95*/
/*Modified 5/97 to use algorithm on p. 110 of Gusfield & Irving*/
/*7/98 added more tracing */

#include <stdio.h>

typedef struct pairStruct pairType;

struct pairStruct {
  int male,maleRank,female,femaleRank;
  pairType *nextFemale,*prevFemale,*nextMale,*prevMale;
};

pairType pair[51][51];

pairType *maleHeader[51],*femaleHeader[51];
int n;

int maleInput[51][51],femaleInput[51][51];

int maleOptimal[51],femaleOptimal[51];

void saveInput()
{
int i,j;

scanf("%d",&n);
for (i=1;i<=n;i++)
  for (j=1;j<=n;j++)
    scanf("%d",&maleInput[i][j]);
for (i=1;i<=n;i++)
  for (j=1;j<=n;j++)
    scanf("%d",&femaleInput[i][j]);
}

void readInput()
{
int i,j,male,female,rank;
pairType *ptr;

for (i=1;i<=n;i++) /*initialization*/
{
  maleHeader[i]= &pair[i][0];  /*initialize male header*/
  ptr=maleHeader[i];
  ptr->male=i;
  ptr->maleRank=0;
  ptr->female=0;
  ptr->femaleRank=0;
  ptr->nextFemale=ptr;
  ptr->prevFemale=ptr;
  ptr->nextMale=NULL;
  ptr->prevMale=NULL;
  femaleHeader[i]= &pair[0][i];  /*initialize female header*/
  ptr=femaleHeader[i];
  ptr->male=0;
  ptr->maleRank=0;
  ptr->female=i;
  ptr->femaleRank=0;
  ptr->nextMale=ptr;
  ptr->prevMale=ptr;
  ptr->nextFemale=NULL;
  ptr->prevFemale=NULL;
  for (j=1;j<=n;j++)
  {
    ptr= &pair[i][j];  /*initialize a pair node*/
    ptr->male=i;
    ptr->maleRank=0;
    ptr->female=j;
    ptr->femaleRank=0;
    ptr->nextFemale=NULL;
    ptr->prevFemale=NULL;
    ptr->nextMale=NULL;
    ptr->prevMale=NULL;
  }
}

for (male=1;male<=n;male++)  /*read men's preference lists*/
  for (rank=1;rank<=n;rank++)
  {
    female=maleInput[male][rank];
    ptr= &pair[male][female];
    if (ptr->maleRank!=0)
    {
      printf("male list has repeat\n");
      abort();
    }
    ptr->maleRank=rank;
    ptr->nextFemale=maleHeader[male];
    ptr->prevFemale=maleHeader[male]->prevFemale;
    maleHeader[male]->prevFemale->nextFemale=ptr;
    maleHeader[male]->prevFemale=ptr;
  }

for (female=1;female<=n;female++)  /*read females' preference lists*/
  for (rank=1;rank<=n;rank++)
  {
    male=femaleInput[female][rank];
    ptr= &pair[male][female];
    if (ptr->femaleRank!=0)
    {
      printf("female list has repeat\n");
      abort();
    }
    ptr->femaleRank=rank;
    ptr->nextMale=femaleHeader[female];
    ptr->prevMale=femaleHeader[female]->prevMale;
    femaleHeader[female]->prevMale->nextMale=ptr;
    femaleHeader[female]->prevMale=ptr;
  }
}

void readInputRolesReversed()
{
int i,j,male,female,rank;
pairType *ptr;

for (i=1;i<=n;i++) /*initialization*/
{
  maleHeader[i]= &pair[i][0];  /*initialize male header*/
  ptr=maleHeader[i];
  ptr->male=i;
  ptr->maleRank=0;
  ptr->female=0;
  ptr->femaleRank=0;
  ptr->nextFemale=ptr;
  ptr->prevFemale=ptr;
  ptr->nextMale=NULL;
  ptr->prevMale=NULL;
  femaleHeader[i]= &pair[0][i];  /*initialize female header*/
  ptr=femaleHeader[i];
  ptr->male=0;
  ptr->maleRank=0;
  ptr->female=i;
  ptr->femaleRank=0;
  ptr->nextMale=ptr;
  ptr->prevMale=ptr;
  ptr->nextFemale=NULL;
  ptr->prevFemale=NULL;
  for (j=1;j<=n;j++)
  {
    ptr= &pair[i][j];  /*initialize a pair node*/
    ptr->male=i;
    ptr->maleRank=0;
    ptr->female=j;
    ptr->femaleRank=0;
    ptr->nextFemale=NULL;
    ptr->prevFemale=NULL;
    ptr->nextMale=NULL;
    ptr->prevMale=NULL;
  }
}

for (male=1;male<=n;male++)  /*read men's preference lists*/
  for (rank=1;rank<=n;rank++)
  {
    female=femaleInput[male][rank];  /*Roles reversed*/
    ptr= &pair[male][female];
    if (ptr->maleRank!=0)
    {
      printf("male list has repeat\n");
      abort();
    }
    ptr->maleRank=rank;
    ptr->nextFemale=maleHeader[male];
    ptr->prevFemale=maleHeader[male]->prevFemale;
    maleHeader[male]->prevFemale->nextFemale=ptr;
    maleHeader[male]->prevFemale=ptr;
  }

for (female=1;female<=n;female++)  /*read females' preference lists*/
  for (rank=1;rank<=n;rank++)
  {
    male=maleInput[female][rank]; /*Roles reversed*/
    ptr= &pair[male][female];
    if (ptr->femaleRank!=0)
    {
      printf("female list has repeat\n");
      abort();
    }
    ptr->femaleRank=rank;
    ptr->nextMale=femaleHeader[female];
    ptr->prevMale=femaleHeader[female]->prevMale;
    femaleHeader[female]->prevMale->nextMale=ptr;
    femaleHeader[female]->prevMale=ptr;
  }
}

void printMatching()
{
int i;

/*Result is the first remaining node on male lists*/
for (i=1;i<=n;i++)
  printf("%d %d\n",i,maleHeader[i]->nextFemale->female);
}

void printPreferenceLists()
{
int i;
pairType *ptr;

printf("male preference lists are:\n");
for (i=1;i<=n;i++)
{
  printf("%d: ",i);
  ptr=maleHeader[i]->nextFemale;
  while (ptr->female!=0)
  {
    printf("%d ",ptr->female);
    if (ptr->nextFemale->prevFemale!=ptr)
      printf("link error\n");
    ptr=ptr->nextFemale;
  }
  printf("\n");
}
printf("female preference lists are:\n");
for (i=1;i<=n;i++)
{
  printf("%d: ",i);
  ptr=femaleHeader[i]->nextMale;
  while (ptr->male!=0)
  {
    printf("%d ",ptr->male);
    if (ptr->nextMale->prevMale!=ptr)
      printf("link error\n");
    ptr=ptr->nextMale;
  }
  printf("\n");
}
}

void galeShapley()
{
/*Finds male-optimal solution and prunes lists*/

int stack[50],sp,i,maleProposer,femaleEngaged[51];
int female;
pairType *ptr;

sp= -1;
for (i=1;i<=n;i++)
{
  sp++;
  stack[sp]=i;
  femaleEngaged[i]=0;
}

/*Gale-Shapley Algorithm*/
while (sp!=(-1))
{
  maleProposer=stack[sp];
  sp--;
  female=maleHeader[maleProposer]->nextFemale->female;
  printf("male %d proposes to female %d\n",maleProposer,female);
  if (femaleEngaged[female])
  {
    /*Female changes engagement, since list deletions*/
    /*guarantee that only better pairs remain for a female*/
    printf("female %d breaks engagement with male %d\n",
      female,femaleHeader[female]->prevMale->male);
    sp++;
    stack[sp]=femaleHeader[female]->prevMale->male;
  }
  else
  {
    printf("first engagement for female %d\n",female);
    femaleEngaged[female]=1;
  }
  ptr=femaleHeader[female]->prevMale;
  while (ptr->male!=maleProposer)
  {
    /*Splice less preferable males for female out of men's lists*/
    printf("Delete male=%d female=%d\n",ptr->male,female);
    ptr->prevFemale->nextFemale=ptr->nextFemale;
    ptr->nextFemale->prevFemale=ptr->prevFemale;
    ptr=ptr->prevMale;
  }
  /*Splice less preferable nodes out of female's list*/
  ptr= &pair[maleProposer][female];
  ptr->nextMale=femaleHeader[female];
  femaleHeader[female]->prevMale=ptr;
  printf("Revised preference lists\n");
  printPreferenceLists();
}
}

void rotations()
{
/* P. 110 of Gusfield & Irving*/
int i,x,m,mprime;
int stack[51],sp,instack[51];
int rhoMale[51],rhoFemale[51],rhoSize;
pairType *ptr;

for (i=1;i<=n;i++)
  instack[i]=0;
sp=(-1);
x=1;
while (x<=n)
{
  if (sp==(-1))
  {
    while (x<=n &&
      maleHeader[x]->nextFemale->female==femaleOptimal[x])
      x++;
    if (x<=n)
    {
      sp++;
      stack[sp]=x;
      instack[x]=1;
    }
  }
  if (sp>(-1))
  {
    m=stack[sp];
    for (m=femaleHeader[maleHeader[m]->nextFemale->nextFemale->female]
           ->prevMale->male;
         !instack[m];
         m=femaleHeader[maleHeader[m]->nextFemale->nextFemale->female]
           ->prevMale->male)
    {
      sp++;
      stack[sp]=m;
      instack[m]=1;
    }
    mprime=stack[sp];
    sp--;
    instack[mprime]=0;
    rhoSize=1;
    rhoMale[0]=mprime;
    rhoFemale[0]=maleHeader[mprime]->nextFemale->female;
    while (m!=mprime)
    {
      mprime=stack[sp];
      sp--;
      instack[mprime]=0;
      rhoMale[rhoSize]=mprime;
      rhoFemale[rhoSize]=maleHeader[mprime]->nextFemale->female;
      rhoSize++;
    }
    printf("Found a rotation:\n");
    for (i=rhoSize-1;i>=0;i--)
      printf("(%d,%d)\n",rhoMale[i],rhoFemale[i]);
    /*List deletions*/
    for (i=rhoSize-1;i>=0;i--)
      while (femaleHeader[rhoFemale[i]]->prevMale->male
        !=rhoMale[(i+1)%rhoSize])
      {
        printf("Delete male=%d female=%d\n",
          femaleHeader[rhoFemale[i]]->prevMale->male,rhoFemale[i]);
        ptr=femaleHeader[rhoFemale[i]]->prevMale;
        ptr->prevFemale->nextFemale=ptr->nextFemale;
        ptr->nextFemale->prevFemale=ptr->prevFemale;
        ptr->prevMale->nextMale=ptr->nextMale;
        ptr->nextMale->prevMale=ptr->prevMale;
    }
    printf("Revised preference lists:\n");
    printPreferenceLists();
    printf("Next matching:\n");
    printMatching();
  }
}
}

main()
{
int i;

saveInput();
readInputRolesReversed();
printf("WARNING-male and female roles reversed while finding female-optimal\n");
printf("Reversed role inputs\n");
printPreferenceLists();
galeShapley();
/*Save/print female-optimal solution*/
for (i=1;i<=n;i++)
  femaleOptimal[i]=femaleHeader[i]->prevMale->male;
printf("female optimal solution\n");
for (i=1;i<=n;i++)
  printf("%d %d\n",i,femaleOptimal[i]);
readInput();
printf("Correct role inputs\n");
printPreferenceLists();
galeShapley();
/*Save male-optimal solution*/
for (i=1;i<=n;i++)
  maleOptimal[i]=maleHeader[i]->nextFemale->female;
printf("Male optimal solution:\n");
printMatching();
rotations();
}