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

typedef struct noeud *abr;
typedef struct chainon *liste;

struct chainon {abr a;liste suite;};
struct noeud {char *nom;abr fg, fd;liste l;};

int comparaison(char *a,char *b){return *a<='9'?strcmp(a+6,b+6)?:strcmp(a+4,b+4):0?:strcmp(a,b);}
#define strcmp comparaison

liste insertiontriee( abr e, liste t )
{ liste d, p=0, n=t;
  while ( n &&  strcmp( n->a->nom, e->nom )<0 ) p=n, n=n->suite;
  if (n && !strcmp( n->a->nom, e->nom )) return t;
  (p?p->suite:t)=d=malloc(sizeof(*d));
  d->a=e;
  d->suite = n;
  return t;
}
abr insertion( char * e, abr n )
{ if(!n) return n=malloc(sizeof(*n)), n->nom=strdup(e), n->fg=n->fd=0, n->l=0, n;
  int s=strcmp(n->nom,e);
  if(s>0) n->fg=insertion(e,n->fg); else
  if(s<0) n->fd=insertion(e,n->fd);
  return n;
}
abr position (abr a,char *e)
{ int s;
  while(a && (s=strcmp(e, a->nom))) a=s<0?a->fg:a->fd;
  return a;
}
void affl(liste l) {for(;l;l=l->suite) printf(" %s", l->a->nom);}

void affa( abr n )
{ for(;n;n=n->fd) affa(n->fg), printf(" %s",n->nom ), affl(n->l), printf("\n");
}
void maj(char *s)
{for(;*s;s++) *s=*s=='é'||*s=='è'?'E':*s>='a'&&*s<='z'?*s-'a'+'A':*s;
}
int main(void)
{ char chauffeur[100], taxi[30];
  abr c = 0, t = 0 ,k, l;
  FILE * fic = fopen( "fabricando", "r" );
  if(!fic) printf("Le fichier fabricando n'existe pas" ), exit( 1 );
  for(;fscanf(fic, "%s%s", chauffeur, taxi )!=-1;)
  { printf("%s a conduit %s\n", chauffeur, taxi);
    maj(chauffeur);
    c=insertion(chauffeur, c);
    t=insertion(taxi     , t);
    k=position(c,chauffeur);
    l=position(t,taxi); 
    k->l=insertiontriee(l,k->l);
    l->l=insertiontriee(k,l->l);
  }
  affa(c); affa(t);
  fclose(fic);
  getchar();
  return 0;
}