/*
This program is a filter ; it computes a summary of a directed graph.
The graph must be strongly connected.

STDIN : a graph description
---------------------------
idx 0
key <some-lable> # ignored
--> idx of a neighbor
--> # one line for each neighbor
idx # more lines for each node
----------------------------

STDOUT : a summary
size <size-of-graph>
dkey 0 d1 d2 d3 ... # d<i> is the number of neighbors at distance <i>
.... # one line for each key
dist <d> <c> # distribution of the distance from a to b with a != b.
             # for <d>, <c> = SUM_{node x} dkey(x, d<d>)
degr <d> <c> # distribution of in-degree ; <c> nodes have in-degree <d>
*/

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

typedef struct TYPE_LINK
  { int idx ;
    struct TYPE_LINK *nxt ;
  } LINK, *LINKREF ;

typedef struct
  { int     idx ;
    int     lncnt ;
    LINKREF links ;
  } POINT ;

#define N 80000
#define R   100

POINT G[N] ;
int size_G = 0 ;
int sigs_G = 0 ;
int res[R] ;
int deg[N] ;

int OPT_Q = 0 ;

LINK *
newLINK (int idx, LINKREF nxt )
{ LINKREF link = (LINK *) malloc ( sizeof ( LINK ) ) ;
  if ( link == NULL ) { perror ( "newLINK" ) ; exit ( 1 ) ; }
  link -> idx = idx ;
  link -> nxt = nxt ;
  return ( link ) ;
}

void
G_get ()
{ int cur ;
  int link ;
  char s[80] ;
  char a[80] ;
  int x ;
  int i ;
  int err = 0 ;

  for ( i=0 ; i < N ; i++ )
    { G[i] . idx = -1 ;
      G[i] . lncnt = 0 ;
      G[i] . links = NULL ;
    }

  while ( scanf ( "%3s %s\n", s, (char *) &a ) != EOF )
    { if ( strcmp ( s, "idx" ) == 0 )
        { x = atoi ( a ) ;
          cur = x ;
          G [ cur ] . idx = cur ;
          size_G ++ ;
        }
      else if ( strcmp ( s, "-->" ) == 0 )
        { x = atoi ( a ) ;
          LINKREF tmp = G [ cur ] . links ;
          G [ cur ] . links = newLINK ( x, tmp ) ;
          G [ cur ] . lncnt ++ ;
          sigs_G ++ ;
        }
      else if ( strcmp ( s, "key" ) == 0 )
        { ; /* ignore */
        }
      else
        { printf ( "unknow tag '%s'\n", s ) ;
          exit ( 1 ) ;
        }
    }

  if ( size_G > N )
    { printf ( "shouldn't happen size_G %d > %d\n", size_G, N ) ;
      exit ( 1 ) ;
    }

  for ( i=0 ; i < size_G ; i++ )
    { if ( G[i] . idx == -1 )
        { printf ( "shouldn't happen G[%d].idx == -1\n", i ) ; err ++ ; }
      if ( G[i] . lncnt == 0 )
        { printf ( "shouldn't happen G[%d].lncnt == 0\n", i ) ; err ++ ; }
      if ( G[i] . lncnt >= N )
        { printf ( "shouldn't happen G[%d].lncnt >= N\n", i ) ; err ++ ; }
      if ( G[i] . links == NULL )
        { printf ( "shouldn't happen G[%d].links == NULL\n", i ) ; err ++ ; }
      else
        { LINKREF p ;
          for ( p = G[i].links ; p != NULL ; p = p -> nxt )
            { int idx = p -> idx ;
              if ( ( idx < 0 ) || ( idx > size_G ) )
                { printf ( "shouldn't happen G[%d] -> %d\n", i, idx ) ; }
            }
        }
    }

  if ( err ) { printf ( "exit ; %d error\n", err ) ; exit ( 1 ) ; }

  for ( i=0 ; i < size_G ; i++ ) { deg [ G[i] . lncnt ] ++ ; }
}

void
print_res ( FILE *fd, int n, int verbose)
{ int i ; int tot = 0 ;

  if ( verbose )
    { fprintf ( stderr, "%5d ----------------\n", n ) ;
/*
      for ( i=0 ; i<R ; i++ ) { tot += res [ i ] ; }
      for ( i=0 ; i<R ; i++ )
        { if ( res [ i ] )
            { fprintf
                ( fd
                , "%d %d %f %5d\n"
                , i
                , res[i]
                , ( 0.0 + res[i] ) / tot
                , size_G
                ) ;
            }
        }
*/
      fflush ( stdout ) ;
      fflush ( stderr ) ;
    }
   else
    { for ( i=0 ; i<R ; i++ )
        { if ( res [ i ] )
            { fprintf ( fd , "dist %3d %d\n" , i , res[i] ) ; }
        }
      for ( i=0 ; i<N ; i++ )
        { if ( deg [ i ] )
            { fprintf ( fd , "degr %3d %d\n" , i , deg[i] ) ; }
        }
    }
}

void
BFS ( FILE *fd, int cur )
{ int queue [N] ;
  int depth [N] ;
  int keyres [R] ;
  int i, head, tail, d ;
  int item, idx ;
  LINKREF links ;

  for ( i=0 ; i < size_G ; i++ ) { depth  [ i ] = -1 ; }
  for ( i=0 ; i < R      ; i++ ) { keyres [ i ] =  0 ; }

  head = 0 ;
  tail = 0 ;
  queue [ tail++ ] = cur ;
  depth [ cur ] = 0 ;

  while ( tail - head )
    { /* printf ( "item %d, |q| %d\n", queue[head], tail - head ) ; */
      item = queue [ head ++ ] ; 
      d = depth [ item ] ;
      for ( links = G[item].links ; links != NULL ; links = links -> nxt )
        { idx = links -> idx ;
          if ( depth [ idx ] < 0 )
            { queue  [ tail++ ] = idx ;
              depth  [ idx ] = d + 1 ;
              keyres [ d + 1 ] ++ ;
#ifdef DEBUG
              if ( tail > N )
                { fprintf ( stderr, "error ; tail %d > %d\n", tail, N ) ;
                  exit ( 1 ) ;
                }
#endif
            }
        }
    }
#ifdef DEBUG
  for ( i = 0 ; i < size_G ; i++ )
    { if ( depth [ i ] == -1 )
        { printf ( "shouldn't happen depth[%d] == -1\n", i ) ; }
    }
#endif
  fprintf ( fd , "dkey %3d" , cur ) ;
  for ( i = 1 ; keyres [ i ] > 0 ; i++ )
    { fprintf ( fd , " %d" , keyres [ i ] ) ;
      res [ i ] += keyres [ i ] ;
    }
  fprintf ( fd , "\n" ) ;
}

main ( argc, argv, envp )
int argc;
char **argv, **envp ;
{ char *prog ;
  prog = argv [ 0 ] ; argc-- ; argv++ ;
  while ( argc && ( argv [ 0 ] [ 0 ]  == '-' ) )
    { if ( 0 == strcmp ( argv [ 0 ], "-q" ) )
        { OPT_Q = 1 ;
          argc-- ; argv++ ;
        }
      else
        { fprintf ( stderr, "%s: unknown option %s\n", prog, argv [ 0 ] ) ;
          exit ( 1 ) ;
        }
    }

  int i ; for ( i = 0 ; i < R ; i++ ) { res [ i ] = 0 ; }

  G_get () ;

  fprintf ( stdout , "size %d\n", size_G ) ;

  for ( i=0 ; i<size_G ; i++ )
    { BFS ( stdout, i ) ;
      if ( ! OPT_Q && ( i % 1000 == 0 ) ) { print_res ( stderr, i, 1) ; }
    } 
  fprintf ( stderr, "sigs in G : %d\n", sigs_G ) ;

  print_res ( stdout, size_G - 1, 0 ) ;

#ifdef DEBUG
  fprintf ( stderr, "debug is : %s\n", "on" ) ;
#endif

  exit ( 0 ) ;

}