Antarctic Scientists

Time limit1sMemory limit128 MB

Summary

Compute the exact character count needed to render an ASCII family tree with fixed box drawing and branching link rules given a forest with up to two children per node.

Level: Hard8 of 10
Topics: Tree, Recursion, Implementation, Simulation
Solved: No attempts yet

Problem

Not long ago, an Antarctic research expedition discovered a new species. To study it, the team extracted a single sample and sent it to their laboratory.

The newly discovered species reproduces on a short cycle. Reproduction needs only one parent, and a single parent can reproduce at most twice; after that it can no longer reproduce.

As a result, the number of specimens in the laboratory grew rapidly, and it became necessary to draw a family tree.

The researchers want to draw the family tree using a simple text editor. The family tree must obey the following rules.

Each specimen's name must be enclosed in a box made of -, |, and o. The center of the top edge and of the bottom edge must carry a + mark. If the length of an edge is even, place the + at the left one of the two central positions.


```
o--+--o
anton
o--+--o
```	```
o----+----o
anamarija
o----+----o
```	```
o-+--o
pero
o-+--o


Boxes must be joined by links. A single link may connect two or more boxes and must attach to a `+`. The parent box is on top and the child box is below. Boxes and links may not overlap.

|                   |                                                           |                                                                               |
| ----------------- | --------------------------------------------------------- | ----------------------------------------------------------------------------- |
| ```
+
|
o
|
+
``` | ```
    +    
    |    
o---o---o
|       |
+       +
``` | ```
      +      
      |      
o-----o-----o
|           |
+           +
``` |

When a node has exactly one child, use the link shown in the leftmost figure. When a node has two or more children, use the branching link, with the older child on the left and the younger child on the right.

A link may be stretched horizontally, and the number of `-` on its left side must equal the number on its right side. A link may not be stretched vertically.

Given the information about each specimen, write a program that computes the number of characters needed to draw the family tree. Spaces are not counted; only `-`, `|`, `+`, `o`, and the name characters are counted.

Input

The first line contains N (1 ≤ N ≤ 300,000), the number of specimens in the laboratory. The specimens are numbered from 1 to N in the order they were born; that is, the oldest specimen is 1 and the youngest is N.

Each of the next N lines contains a specimen's name and its parent's number. (The parent of the first specimen is unknown.) A name is a string of lowercase letters whose length does not exceed 20.

Output

Print, on the first line, the number of characters needed to draw the family tree.

Examples3

Example 1
Input
```
3
adam
kain 1
abel 1
```
Expected output
```
64
```

Example 2

Input

12
anton
ana 1
luka 1
mia 2
tea 3
jakov 3
semiramida 5
dominik 5
anamarija 4
eustahije 4
lovro 2
lovro 11

Expected output

Example 3
Input
```
1
q
```
Expected output
```
9
```