1409. Links

Let `(V,\ E)` be a directed graph in which `V` is a finite set of vertices and `E\ sube\ V\ times\ V` is a set of edges such that `||{\ q\ |\ (p,\ q)\ "isin"\ E\ }||\ ≤\ 1` for all `p\ "isin"\ V`. In other words, `E` can be viewed as a predecessor-successor relation on vertices in which each vertex has at most one successor. Such a graph can be seen to contain embedded lists-sequences of vertices `v_1,\ v_2,\ …,\ v_n` in which `v_1` has no predecessor, `v_{i+1}` is the successor of `v_i` for `i\ =\ 1,\ 2,\ …,\ n-1`, and `v_n` has no successor. In this problem, you are given a directed graph in which vertices have at most one successor, and are asked to count the number of embedded lists and compute the average number of vertices in those lists.

Input Format

The input contains one or more directed graphs, each of which is described on one or more nonempty lines of input followed by an empty line of input. Each nonempty line of input in a graph contains one or more pairs of vertices. The vertices are non-white-space ASCII characters separated by one or more blanks. The pairs of vertices in a graph form the predecessor-successor relation of the graph. To insure that no vertex has more than one successor, if there are multiple pairs having the same predecessor, then their vertices are included and their edges except the last are ignored (e.g. as in the second graph in the input sample below).

Output Format

For each directed graph in the input, count the number of embedded lists containing at least one vertex, and compute the average number of vertices in those lists, rounded to two decimal places as shown in the output sample.

a b   b c   c d   d e

a b
a c
a d

a b   b c   c a

a c
b c   c d   d e
g h   h i   i h

1 lists averaging 5.00 vertices
3 lists averaging 1.33 vertices
0 lists
2 lists averaging 4.00 vertices