Directory Traversal#10412

Directory Traversal

1 second

128 megabytes

Easy

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 move into any directory she wants. From the current directory, any file can be referenced by a relative path, in which the symbol .. denotes the parent directory. For example, if Bessie is in folder2, she can refer to the four files as follows:

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

Bessie wants to choose a directory from which the total length of the relative paths to all files is as small as possible.

Input

The first line contains an integer $n (2 \leq n \leq 1 0^{5})$ n~(2 \le n \le 10^5) — the total number of files and directories. Each object (a file or a directory) is assigned a unique integer ID from $1$ to $n$ , where ID $1$ corresponds to the top-level directory.

Each of the next $n$ lines describes one object. A line starts with the name of the file or directory. The name consists only of lowercase Latin letters (' $a$ ' – ' $z$ ') and digits (' $0$ ' – ' $9$ '), and its length does not exceed $16$ characters. The name is followed by an integer $m$ . If $m = 0$ m = 0, the object is a file. If $m > 0$ m > 0, the object is a directory that directly contains $m$ files or directories; in this case, $m$ integers follow — the IDs of the objects in this directory.

Output

Print the minimum possible total length of the relative paths to all files. Note that this value may not fit into a $32$ -bit integer.

Examples

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

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

Example 1