Bessie the cow is surprisingly computer savvy. On her computer in the barn, she
stores all of her precious files in a collection of directories; for example:

bessie/
folder1/
file1
folder2/
file2
folder3/
file3
file4

There is a single "top level" directory, called bessie.

Bessie can navigate to be inside any directory she wants. From a given
directory, any file can be referenced by a "relative path". In a relative path,
the symbol ".." refers to the parent directory. If Bessie were in folder2, she
could refer to the four files as follows:

../file1
file2
../../folder3/file3
../../file4

Bessie would like to choose a directory from which the sum of the lengths of the
relative paths to all the files is minimized.

INPUT FORMAT:
The first line contains an integer N ($2 \leq N \leq 100,000$), giving the total
number of files and directories. For the purposes of input, each object (file
or directory) is assigned a unique integer ID between 1 and $N$, where ID 1
refers to the top level directory.

Next, there will be $N$ lines. Each line starts with the name of a file or
directory. The name will have only lower case characters a-z and digits 0-9, and
will be at most 16 characters long. Following the name is an integer, $m$. If
$m$ is 0, then this entity is a file. If $m > 0$, then this entity is a
directory, and it has a total of $m$ files or directories inside it. Following $m$
there will be $m$ integers giving the IDs of the entities in this directory.

OUTPUT FORMAT:
Output the minimal possible total length of all relative paths to files. Note
that this value may be too large to fit into a 32-bit integer.

SAMPLE INPUT:
8
bessie 3 2 6 8
folder1 2 3 4
file1 0
folder2 1 5
file2 0
folder3 1 7
file3 0
file4 0
SAMPLE OUTPUT:
42

This input describes the example directory structure given above.

The best solution is to be in folder1. From this directory, the relative paths
are:

file1
folder2/file2
../folder3/file3
../file4

Problem credits: Mark Gordon

见题面

见题面