남극의 과학자

시간 제한

1초

메모리 제한

128 MB

문제

얼마 전 남극 연구 탐사대가 새로운 종을 발견했다. 연구진은 연구를 위해 표본 하나를 추출하여 연구실로 보냈다.

이번에 발견된 새로운 종은 짧은 주기로 번식한다. 번식에는 부모가 하나만 있으면 되고, 한 부모는 최대 두 번까지 번식할 수 있으며 그 이후에는 더 이상 번식하지 못한다.

그 결과 연구실에 있는 표본의 수가 급격히 늘어났고, 가계도가 필요한 시점이 되었다.

연구진은 간단한 텍스트 에디터로 가계도를 그리려고 한다. 가계도는 다음 규칙을 지켜야 한다.

각 표본의 이름은 -, |, o로 이루어진 박스로 둘러싸여 있어야 한다. 윗변과 아랫변의 중앙에는 + 표시가 있어야 한다. 변의 길이가 짝수이면 두 중앙 위치 중 왼쪽에 +를 놓는다.


박스는 링크로 연결해야 한다. 하나의 링크는 두 개 이상의 박스를 연결할 수 있으며, 반드시 `+`에 연결되어야 한다. 부모 박스는 위에, 자식 박스는 아래에 있어야 한다. 박스와 링크는 서로 겹칠 수 없다.
|                   |                                                           |                                                                               || ----------------- | --------------------------------------------------------- | ----------------------------------------------------------------------------- || ```+|o|+``` | ```    +        |    o---o---o|       |+       +``` | ```      +            |      o-----o-----o|           |+           +``` |
자식이 한 명인 경우에는 가장 왼쪽 그림의 링크를 사용한다. 자식이 둘 이상인 경우에는 가운데에서 갈라지는 링크를 사용하며, 왼쪽에 나이가 많은 자식을, 오른쪽에 나이가 적은 자식을 둔다.
링크는 수평 방향으로 늘일 수 있으며, 이때 왼쪽과 오른쪽의 `-` 개수는 같아야 한다. 링크는 수직 방향으로는 늘일 수 없다.
각 표본의 정보가 주어졌을 때, 가계도를 그리는 데 필요한 문자의 개수를 구하는 프로그램을 작성하시오. 단, 공백은 세지 않고 `-`, `|`, `+`, `o`와 이름 글자만 센다.


박스는 링크로 연결해야 한다. 하나의 링크는 두 개 이상의 박스를 연결할 수 있으며, 반드시 `+`에 연결되어야 한다. 부모 박스는 위에, 자식 박스는 아래에 있어야 한다. 박스와 링크는 서로 겹칠 수 없다.
|                   |                                                           |                                                                               || ----------------- | --------------------------------------------------------- | ----------------------------------------------------------------------------- || ```+|o|+``` | ```    +        |    o---o---o|       |+       +``` | ```      +            |      o-----o-----o|           |+           +``` |
자식이 한 명인 경우에는 가장 왼쪽 그림의 링크를 사용한다. 자식이 둘 이상인 경우에는 가운데에서 갈라지는 링크를 사용하며, 왼쪽에 나이가 많은 자식을, 오른쪽에 나이가 적은 자식을 둔다.
링크는 수평 방향으로 늘일 수 있으며, 이때 왼쪽과 오른쪽의 `-` 개수는 같아야 한다. 링크는 수직 방향으로는 늘일 수 없다.
각 표본의 정보가 주어졌을 때, 가계도를 그리는 데 필요한 문자의 개수를 구하는 프로그램을 작성하시오. 단, 공백은 세지 않고 `-`, `|`, `+`, `o`와 이름 글자만 센다.

입력

첫째 줄에 연구실에 있는 표본의 수 N (1 ≤ N ≤ 300,000)이 주어진다. 각 표본은 태어난 순서대로 1번부터 N번까지 번호가 매겨져 있다. 즉, 가장 나이가 많은 표본이 1번이고 가장 어린 표본이 N번이다.

다음 N개의 줄에는 각 표본의 이름과 부모의 번호가 주어진다. (첫 번째 표본의 부모는 알 수 없다.) 이름은 알파벳 소문자로만 이루어진 문자열이며 길이는 20을 넘지 않는다.

출력

첫째 줄에 가계도를 그리는 데 필요한 문자의 개수를 출력한다.


박스는 링크로 연결해야 한다. 하나의 링크는 두 개 이상의 박스를 연결할 수 있으며, 반드시 `+`에 연결되어야 한다. 부모 박스는 위에, 자식 박스는 아래에 있어야 한다. 박스와 링크는 서로 겹칠 수 없다.
|                   |                                                           |                                                                               || ----------------- | --------------------------------------------------------- | ----------------------------------------------------------------------------- || ```+|o|+``` | ```    +        |    o---o---o|       |+       +``` | ```      +            |      o-----o-----o|           |+           +``` |
자식이 한 명인 경우에는 가장 왼쪽 그림의 링크를 사용한다. 자식이 둘 이상인 경우에는 가운데에서 갈라지는 링크를 사용하며, 왼쪽에 나이가 많은 자식을, 오른쪽에 나이가 적은 자식을 둔다.
링크는 수평 방향으로 늘일 수 있으며, 이때 왼쪽과 오른쪽의 `-` 개수는 같아야 한다. 링크는 수직 방향으로는 늘일 수 없다.
각 표본의 정보가 주어졌을 때, 가계도를 그리는 데 필요한 문자의 개수를 구하는 프로그램을 작성하시오. 단, 공백은 세지 않고 `-`, `|`, `+`, `o`와 이름 글자만 센다.


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