/* Solves for a single solution (if any) of stable roommates*/
/* BP Weems 5/9/97*/

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

typedef struct pairStruct pairType;

struct pairStruct {
  int listOwner,possiblePartner,ownerRank;
  pairType *nextPossible,*prevPossible;
};

pairType pair[51][51];
pairType *header[51];
int n;

void readInput()
{
int i,j,listOwner,possiblePartner,rank;
pairType *ptr;
scanf("%d",&n);

/*Initialize structure*/
for (i=1;i<=n;i++)
{
  ptr=header[i]= &pair[i][0];
  ptr->listOwner=i;
  ptr->possiblePartner=0;
  ptr->ownerRank=0;
  ptr->nextPossible=ptr;
  ptr->prevPossible=ptr;
  for (j=1;j<=n;j++)
  {
    ptr= &pair[i][j];
    ptr->listOwner=i;
    ptr->possiblePartner=j;
    ptr->ownerRank=0;
    ptr->nextPossible=NULL;
    ptr->prevPossible=NULL;
  }
}

for (listOwner=1;listOwner<=n;listOwner++)
  for (rank=1;rank<n;rank++)
  {
    scanf("%d",&possiblePartner);
    if (listOwner==possiblePartner)
    {
      printf("Individual in own preference list %d\n",listOwner);
      exit(0);
    }
    ptr= &pair[listOwner][possiblePartner];
    if (ptr->ownerRank!=0)
    {
      printf("Duplicate in preference list %d\n",listOwner);
      exit(0);
    }
    ptr->ownerRank=rank;
    ptr->nextPossible=header[listOwner];
    ptr->prevPossible=header[listOwner]->prevPossible;
    header[listOwner]->prevPossible->nextPossible=ptr;
    header[listOwner]->prevPossible=ptr;
  }
}

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

for (i=1;i<=n;i++)
{
  printf("%d: ",i);
  for (ptr=header[i]->nextPossible;
       ptr!=header[i];
       ptr=ptr->nextPossible)
    printf("%d ",ptr->possiblePartner);
  printf("\n");
}
}

int phase1()
/* See Gusfield & Irving, p. 167*/
{
int freeStack[51],sp=(-1);
int semiEngaged[51]; /* semiEngaged[i] contains the
                        person semiengaged to i */
int x,xprime,y,z,i;

for (i=1;i<=n;i++)
{
  sp++;
  freeStack[sp]=i;
  semiEngaged[i]=0;
}

while (sp!=(-1))
{
  x=freeStack[sp];
  sp--;
  if (header[x]->nextPossible==header[x])
  {
    printf("phase 1 has empty list for %d - no solution exists\n",x);
    return 0;
  }
  y=header[x]->nextPossible->possiblePartner;
  z=semiEngaged[y];
  if (z!=0)
  {
    sp++;
    freeStack[sp]=z;
  }
  printf("debug: semiEngaged[%d]=%d\n",y,x);
  semiEngaged[y]=x;
  for (xprime=pair[y][x].nextPossible->possiblePartner;
       xprime!=0;
       xprime=pair[y][x].nextPossible->possiblePartner)
  {
    printf("debug: delete {%d %d} from lists\n",y,xprime);
    pair[y][xprime].prevPossible->nextPossible=
      pair[y][xprime].nextPossible;
    pair[y][xprime].nextPossible->prevPossible=
      pair[y][xprime].prevPossible;
    pair[xprime][y].prevPossible->nextPossible=
      pair[xprime][y].nextPossible;
    pair[xprime][y].nextPossible->prevPossible=
      pair[xprime][y].prevPossible;
  }
  printf("debug:  after processing semiengagement\n");
  printTable();
}
return 1;
}

int haveSolution()
{
int i;

for (i=1;i<=n;i++)
  if (header[i]->nextPossible==header[i] ||
  (header[i]->nextPossible!=header[i]->prevPossible))
    return 0;
return 1;
}

void phase2()
/* See Gusfield & Irving, p. 184 */ 
{
int stack[51],sp;
int inStack[51];
int x,p,pprime,qprime,emptylist,i;
int rhoX[51],rhoY[51],rhoSize;
int deleteU,deleteV;

emptylist=0;
sp=(-1);
for (i=1;i<=n;i++)
  inStack[i]=0;

/*Find lowest numbered person with at least 2 list entries*/
for (x=1;
     header[x]->nextPossible==header[x]->prevPossible;
     x++)
  ;

while (x<=n && !emptylist)
{
  if (sp==(-1))
  {
    while (x<=n &&
      header[x]->nextPossible==header[x]->prevPossible)
      x++;
    if (x<=n)
    {
      sp++;
      stack[sp]=x;
      inStack[x]=1;
    }
  }

  if (sp>(-1))
  {
    printTable();
    p=stack[sp];
    /*Very bottom of p. 173 explains this*/
    p=header[header[p]->nextPossible->nextPossible->possiblePartner]
        ->prevPossible->possiblePartner;
    while (!inStack[p])
    {
      sp++;
      stack[sp]=p;
      inStack[p]=1;
      /*Again, see very bottom of P. 173*/
      p=header[header[p]->nextPossible->nextPossible->possiblePartner]
          ->prevPossible->possiblePartner;
    }
    pprime=stack[sp];
    sp--;
    inStack[pprime]=0;
    /*Note: rotation is reversed from usual Gusfield & Irving order*/
    rhoSize=1;
    rhoX[0]=pprime;
    rhoY[0]=header[pprime]->nextPossible->possiblePartner;
    while (pprime!=p)
    {
      pprime=stack[sp];
      sp--;
      inStack[pprime]=0;
      rhoX[rhoSize]=pprime;
      rhoY[rhoSize]=header[pprime]->nextPossible->possiblePartner;
      rhoSize++;
    }
    printf("DEBUG-rotation: ");
    for (i=rhoSize-1;i>=0;i--)
      printf("(%d,%d)",rhoX[i],rhoY[i]);
    printf("\n");
    for (i=0;i<rhoSize;i++)
    {
      pprime=rhoX[i];
      qprime=rhoY[i];
      while (1)
      {
        deleteU=qprime;
        deleteV=header[qprime]->prevPossible->possiblePartner;
        if (deleteV==0)
        {
          printf("phase 2 cannot find solution\n");
          return;
        }
        else if (deleteV==rhoX[(i+1)%rhoSize])
          break;
        else
        {
          printf("debug: delete {%d %d} from lists\n",deleteU,deleteV);
          pair[deleteU][deleteV].prevPossible->nextPossible=
            pair[deleteU][deleteV].nextPossible;
          pair[deleteU][deleteV].nextPossible->prevPossible=
            pair[deleteU][deleteV].prevPossible;
          pair[deleteV][deleteU].prevPossible->nextPossible=
            pair[deleteV][deleteU].nextPossible;
          pair[deleteV][deleteU].nextPossible->prevPossible=
            pair[deleteV][deleteU].prevPossible;
        }
      }
    }
    /* Patch to G & I algorithm!!!! */
    while (1)
      if (sp==(-1))
        break;
      else if (header[stack[sp]]->nextPossible==
               header[stack[sp]]->prevPossible)
        sp--;
      else
        break;
  }
}

if (emptylist)
  printf("phase 2 cannot find solution\n");
else
  printf("phase 2 has solution\n");
}

int main()
{
readInput();
printf("Input:\n");
printTable();
if (phase1())
{
  printf("After phase 1:\n");
  printTable();
  if (haveSolution())
  {
    printf("phase 2 not needed\n");
    exit(0);
  }
  phase2();
  printf("After phase 2:\n");
  printTable();
}
else
  printTable();
}