Directory Traversal

Bessie the cow is surprisingly good with computers. On the computer in her barn she keeps her files spread across a set of directories, like this one.

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

There is exactly one top level directory, and its name is bessie.

Bessie can move into any directory she likes. From whichever directory she is in she can refer to every file by a relative path, and in a relative path .. means the parent directory. If Bessie were inside folder2, she would refer to the four files like this.

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

A relative path goes up from the current directory to the closest common ancestor of that directory and the target file, then down to the file. Each step up is written as .., each step down is written as the name of that directory or file, and the components are joined with /. The length of a path is the number of characters in the string built this way.

Bessie wants to pick the directory that minimizes the sum of the lengths of the relative paths to all of the files.

The first line contains the total number of files and directories $N$ ($2 \le N \le 100\,000$). In the input, every file and directory is given a distinct integer ID between 1 and $N$, and ID 1 is the top level directory.

The next $N$ lines describe the file or directory with ID 1 through $N$, in that order. Each line starts with a name. A name uses only the lower case letters a to z and the digits 0 to 9, and is at most 16 characters long. After the name comes an integer $m$. If $m$ is 0, this object is a file. If $m > 0$, this object is a directory holding $m$ files or directories in total. After $m$ come the $m$ IDs of the objects inside that directory.

Print the smallest possible sum of the lengths of the relative paths to all of the files. This value may not fit in a 32-bit integer.

The input of the first example describes the directory structure shown in the statement. The best choice is folder1, and from that directory the relative paths to the files are these.

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