#include<stdio.h>
#include<stdlib.h>
#if 0
#define N 4
#define A 6
#elif 0
#define N 10
#define A (2*N)
#else
#define X 7
#define Y 9
#define Z (X+Y+1)
#define N ((X+1)*(Y+1))
#define A (6*N)
#endif
typedef char graphe1[N][N];
typedef int sommet;
typedef sommet graphe2[2*A];
typedef struct maillon maillon, *liste;
struct maillon { sommet s; liste next; } ;
typedef liste graphe3[N];
void affg1(graphe1 g1)
{ for(int i=0;i<N;i++)
  for(int j=0;j<N;j++)
  if(g1[i][j]) printf("%d-->%d ",i,j);
  printf("\n");
}
void affg2(graphe2 g2)
{ for(int k=0;k<2*A;k+=2) printf("%d-->%d ",g2[k],g2[k+1]);
  printf("\n");
}
void affg3(graphe3 g3)
{ for(int i=0;i<N;i++)
  for(liste l=g3[i];l;l=l->next) printf("%d-->%d ",i,l->s);
  printf("\n");
}
void g1g2(graphe1 g1, graphe2 g2)
{ for(int i=0;i<N;i++)
  for(int j=0;j<N;j++)
  if(g1[i][j])
  *g2++=i, *g2++=j;
}
void g1g3(graphe1 g1, graphe3 g3, maillon t[A])
{ for(int i=0;i<N;i++)
  { liste l=0;
    for(int j=0;j<N;j++)
    if(g1[i][j])
    t->s=j, t->next=l, l=t++;
    g3[i]=l;
  }
}
void g2g1(graphe2 g2, graphe1 g1)
{ for(int i=0;i<N;i++)
  for(int j=0;j<N;j++) g1[i][j]=0;
  for(int k=0;k<2*A;k+=2) g1[g2[k]][g2[k+1]]=1;
}
void g2g3(graphe2 g2, graphe3 g3, maillon t[A])
{ for(int i=0;i<N;i++) g3[i]=0;
  for(int k=0;k<2*A;k+=2)
  { int i=g2[k];
    t->s=g2[k+1], t->next=g3[i], g3[i]=t++;
  }
}
void g3g1(graphe3 g3, graphe1 g1)
{ for(int i=0;i<N;i++)
  { for(int j=0;j<N;j++) g1[i][j]=0;
    for(liste l=g3[i];l;l=l->next) g1[i][l->s]=1;
  }
}
void g3g2(graphe3 g3, graphe2 g2)
{ for(int i=0;i<N;i++)
  for(liste l=g3[i];l;l=l->next) *g2++=i, *g2++=l->s;
}
void retourneg1(graphe1 g1)
{ for(int i=0;i<N;i++)
  for(int j=0;j<i;j++)
  { int x=g1[i][j]; g1[i][j]=g1[j][i]; g1[j][i]=x; }
}
void retourneg2(graphe2 g2)
{ for(int k=0;k<2*A;k+=2)
  { int x=g2[k]; g2[k]=g2[k+1]; g2[k+1]=x; }
}
void retourneg3(graphe3 g3)
{ graphe3 h3;
  for(int i=0;i<N;i++) h3[i]=g3[i], g3[i]=0;
  for(int i=0;i<N;i++)
  for(liste p=h3[i];p;)
  { int    j=p->s;     p->s=i;
    liste q=p->next;  p->next=g3[j], g3[j]=p, p=q;
  }
}
int cherchecfc1(graphe1 g1, int cfc[N])
{ int nbcfc=0, nbfin=0, fin[N];
  void parcours1(int s)
  { cfc[s]=-1;
    for(int i=0;i<N;i++) if(g1[s][i] && !cfc[i]) parcours1(i);
    fin[nbfin++]=s;
  }
  void parcours2(int s)
  { cfc[s]=nbcfc;
    for(int i=0;i<N;i++) if(g1[i][s] && cfc[i]<0) parcours2(i);
  }
  int i;
  for(i=0;i<N;i++) cfc[i]=0;
  for(i=0;i<N;i++) if(!cfc[i]) parcours1(i);
  while(nbfin) if(cfc[i=fin[--nbfin]]<0) parcours2(i), nbcfc++;
  return nbcfc;
}
int cherchecfc2(graphe2 g2, int cfc[N])
{ int nbcfc=0, nbfin=0, fin[N];
  graphe3 g3;
  void parcours1(int s)
  { cfc[s]=-1;
    for(liste p=g3[s];p;p=p->next) if(!cfc[p->s]) parcours1(p->s);
    fin[nbfin++]=s;
  }
  void parcours2(int s)
  { cfc[s]=nbcfc;
    for(liste p=g3[s];p;p=p->next) if(cfc[p->s]<0) parcours2(p->s);
  }
  int i;
  for(i=0;i<N;i++) cfc[i]=0;
  maillon m3[A];
  g2g3(g2,g3,m3);
  for(i=0;i<N;i++) if(!cfc[i]) parcours1(i);
  retourneg3(g3);
  while(nbfin) if(cfc[i=fin[--nbfin]]<0) parcours2(i), nbcfc++;
  retourneg3(g3);
  return nbcfc;
}
int cherchecfc3(graphe3 g3, int cfc[N])
{ int nbcfc=0, nbfin=0, fin[N];
  void parcours1(int s)
  { cfc[s]=-1;
    for(liste p=g3[s];p;p=p->next) if(!cfc[p->s]) parcours1(p->s);
    fin[nbfin++]=s;
  }
  void parcours2(int s)
  { cfc[s]=nbcfc;
    for(liste p=g3[s];p;p=p->next) if(cfc[p->s]<0) parcours2(p->s);
  }
  int i;
  for(i=0;i<N;i++) cfc[i]=0;
  for(i=0;i<N;i++) if(!cfc[i]) parcours1(i);
  retourneg3(g3);
  while(nbfin) if(cfc[i=fin[--nbfin]]<0) parcours2(i), nbcfc++;
  retourneg3(g3);
  return nbcfc;
}
void afft(int *t, int i) { while(i--) printf("%d ",*t++); printf("\n"); }

void pluscourt1(graphe1 g1,sommet s,int dist[N],int pere[N])
{ int file[N], in=0, out=0, i;
  for(i=0;i<N;i++) dist[i]=pere[i]=-1;
  dist[file[in++]=s]=0, pere[s]=s;
  while(out<in)
  { s=file[out++];
    for(i=0;i<N;i++) if(g1[s][i]) if(dist[i]<0) dist[file[in++]=i]=dist[s]+1, pere[i]=s;
  }
}
void pluscourt2(graphe2 g2,sommet s,int dist[N],int pere[N])
{ int file[N], in=0, out=0, i;
  graphe3 g3;
  maillon m3[A];
  g2g3(g2,g3,m3);
  for(i=0;i<N;i++) dist[i]=pere[i]=-1;
  dist[file[in++]=s]=0, pere[s]=s;
  while(out<in)
  { s=file[out++];
    for(liste p=g3[s];p;p=p->next) if(dist[i=p->s]<0) dist[file[in++]=i]=dist[s]+1, pere[i]=s;
  }
}
void pluscourt3(graphe3 g3,sommet s,int dist[N],int pere[N])
{ int file[N], in=0, out=0, i;
  for(i=0;i<N;i++) dist[i]=pere[i]=-1;
  dist[file[in++]=s]=0, pere[s]=s;
  while(out<in)
  { s=file[out++];
    for(liste p=g3[s];p;p=p->next) if(dist[i=p->s]<0) dist[file[in++]=i]=dist[s]+1, pere[i]=s;
  }
}
void affpluscourt(int pere[N],int b)
{ if(pere[b]<0) printf("pas de chemin vers"); else
  if(pere[b]!=b) affpluscourt(pere,pere[b]);
  printf(" %d",b);
}
void minimise(int *a,int b) { if(b<*a) *a=b; }
int cherchecfc3pile(graphe3 g3,int cfc[N])
{ int num[N], min[N], c=0, pile[N], ip=0, nbcfc=N, i;
  int parcours(int s)
  { if(cfc[s]>=0) return N;
    if(min[s]>=0) return min[s];
    num[s]=min[s]=c++, pile[ip++]=s;
    for(liste p=g3[s];p;p=p->next) minimise(min+s,parcours(p->s));
    if(min[s]==num[s]) for(nbcfc--;cfc[pile[--ip]]=nbcfc,s!=pile[ip];) ;
    return min[s];
  }
  for(i=0;i<N;i++) min[i]=cfc[i]=-1;
  for(i=0;i<N;i++) parcours(i);
  for(i=0;i<N;i++) cfc[i]-=nbcfc;
  return N-nbcfc;
}
int cherchecfc3pil(graphe3 g3,int cfc[N])
{ int c=0, pile[N], ip=0, nbcfc=N, i;
  int parcours(int s)
  { if(cfc[s]>=0) return cfc[s];
    cfc[s]=c++, pile[ip++]=s;
    for(liste p=g3[s];p;p=p->next) minimise(cfc+s,parcours(p->s));
    if(cfc[s]==--c) for(nbcfc--;cfc[pile[--ip]]=nbcfc,s!=pile[ip];) ;
    return cfc[s];
  }
  for(i=0;i<N;i++) cfc[i]=-1;
  for(i=0;i<N;i++) parcours(i);
  for(i=0;i<N;i++) cfc[i]-=nbcfc;
  return N-nbcfc;
}
int cherchecfc3pi(graphe3 g3,int cfc[N])
{ int c=0, pile[N], ip=0, nbcfc=N, i;
  void parcours(int s)
  { cfc[s]=c++, pile[ip++]=s;
    for(liste p=g3[s];p;minimise(cfc+s,cfc[p->s]),p=p->next) if(cfc[p->s]<0) parcours(p->s);
    if(cfc[s]==--c) for(nbcfc--;cfc[pile[--ip]]=nbcfc,s!=pile[ip];) ;
  }
  for(i=0;i<N;i++) cfc[i]=-1;
  for(i=0;i<N;i++) if(cfc[i]<0) parcours(i);
  for(i=0;i<N;i++) cfc[i]-=nbcfc;
  return N-nbcfc;
}
int cherchecfc3it(graphe3 h3,int cfc[N])
{ int c=0, pile[N], ip=0, nbcfc=N, i, s, pile2[N];
  graphe3 g3;
  for(i=0;i<N;i++) cfc[i]=-1, g3[i]=h3[i];
  for(i=0;i<N;i++)
  { s=i;
    entree: if(cfc[s]>=0) goto sortie;
    pile2[cfc[s]=c++]=pile[ip++]=s;
//  for(;g3[s];minimise(cfc+s,cfc[g3[s]->s]),g3[s]=g3[s]->next) if(cfc[g3[s]->s]<0) parcours(g3[s]->s);
    next: if(g3[s]) { s=g3[s]->s; goto entree; }
    if(cfc[s]==--c) for(nbcfc--;cfc[pile[--ip]]=nbcfc,s!=pile[ip];) ;
    sortie: if(!c) continue;
    s=pile2[c-1], minimise(cfc+s,cfc[g3[s]->s]), g3[s]=g3[s]->next;
    goto next;
  }
  for(i=0;i<N;i++) cfc[i]-=nbcfc;
  return N-nbcfc;
}
#ifdef X
typedef struct { int a, b, c, aa, bb, cc; } seaux;
seaux verse(seaux s) { s.b=s.a+=s.b, minimise(&s.b,s.bb), s.a-=s.b; return s; }
seaux s1(seaux s) { int x=s.a; s.a=s.b, s.b=x, x=s.aa, s.aa=s.bb, s.bb=x; return s; }
seaux s2(seaux s) { int x=s.a; s.a=s.c, s.c=x, x=s.aa, s.aa=s.cc, s.cc=x; return s; }
int code(seaux s) { return s.a*(Y+1)+s.b; }
seaux decode(int s) { int a=s/(Y+1), b=s%(Y+1); return (seaux){a,b,Z-a-b,X,Y,Z}; }
void affseaux(int t) { seaux s=decode(t); printf("(%d,%d,%d)",s.a,s.b,s.c); }
void setseaux(graphe3 g3)
{ graphe2 g2;
  for(int i=0,k=0;i<N;i++)
  g2[k++]=i, g2[k++]=code(verse(decode(i))),
  g2[k++]=i, g2[k++]=code(s1(verse(s1(decode(i))))),
  g2[k++]=i, g2[k++]=code(s2(verse(s2(decode(i))))),
  g2[k++]=i, g2[k++]=code(s1(s2(verse(s2(s1(decode(i))))))),
  g2[k++]=i, g2[k++]=code(s2(s1(verse(s1(s2(decode(i))))))),
  g2[k++]=i, g2[k++]=code(s1(s2(s1(verse(s1(s2(s1(decode(i)))))))));
  g2g3(g2,g3,malloc(A*sizeof(maillon)));
}
void affpluscourtseaux(int pere[N],int b)
{ if(pere[b]<0) printf("pas de chemin vers"); else
  if(pere[b]!=b) affpluscourtseaux(pere,pere[b]);
  affseaux(b);
}
void probleme(graphe3 g3)
{ int pere[N], dist[N], i;
  pluscourt3(g3,0,dist,pere); // afft(dist,N), afft(pere,N);
  for(i=0;i<N;i+=Y+1) affpluscourtseaux(pere,i), printf("\n");
  for(i=0;i<=Y;i++)   affpluscourtseaux(pere,i), printf("\n");
}
#endif
int main()
{ graphe1 h1, f1, g1={{0,1,0,1}, {0,0,1,1}, {1,0,0,0}, {0,0,1,0}};
  graphe2 h2, f2, g2={ 1,2, 3,2, 0,3, 1,3, 2,0, 0,1 };
  maillon tmh3[A], tmf3[A], m1={1,0}, m2={3,&m1}, m3={2,0}, m4={3,&m3}, m5={0,0}, m6={2,0};
  graphe3 h3, f3, g3={&m2, &m4, &m5, &m6};
#ifdef X
  setseaux(g3), probleme(g3); return 0;
#endif  
  if(N!=4 || A!=6)
  { for(int k=0,i=0;i<N;i++) g2[k++]=i, g2[k++]=(i+1)%N, g2[k++]=i, g2[k++]=(i+2)%N; 
    for(int k=0,z=6;k<2*A;k+=2) if((z=103*z+1)&128) { int x=g2[k]; g2[k]=g2[k+1], g2[k+1]=x; }
    g2g1(g2,g1);
    g1g3(g1,g3,malloc(A*sizeof(maillon)));
  }
  affg1(g1);
  affg2(g2);
  affg3(g3);
  g1g2(g1,f2), affg2(f2);
  g2g1(g2,h1), affg1(h1);
  g3g2(g3,h2), affg2(h2);
  g3g1(g3,f1), affg1(f1);
  g1g3(g1,h3,tmh3), affg3(h3);
  g2g3(g2,f3,tmf3), affg3(f3);
  int cfc[N];
  printf("nbcfc=%d   ",cherchecfc1(g1,cfc)); afft(cfc,N);
  printf("nbcfc=%d   ",cherchecfc2(g2,cfc)); afft(cfc,N);
  printf("nbcfc=%d   ",cherchecfc3(g3,cfc)); afft(cfc,N);
  printf("nbcfc=%d   ",cherchecfc3pile(g3,cfc)); afft(cfc,N);
  printf("nbcfc=%d   ",cherchecfc3pil (g3,cfc)); afft(cfc,N);
  printf("nbcfc=%d   ",cherchecfc3pi  (g3,cfc)); afft(cfc,N);
  printf("nbcfc=%d   ",cherchecfc3it  (g3,cfc)); afft(cfc,N);
  int pere[N], dist[N], i;
  pluscourt1(g1,0,dist,pere), afft(dist,N), afft(pere,N);
  pluscourt2(g2,0,dist,pere), afft(dist,N), afft(pere,N);
  pluscourt3(g3,0,dist,pere), afft(dist,N), afft(pere,N);
  for(i=0;i<N;i++) affpluscourt(pere,i), printf("\n");
  return 0;
}