디렉터리 순회

소 베시는 의외로 컴퓨터를 잘 다룬다. 외양간에 있는 컴퓨터에서 베시는 아끼는 파일을 여러 디렉터리에 나누어 보관한다. 예를 들면 다음과 같은 구조다.

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

최상위 디렉터리는 하나뿐이고 이름은 bessie다.

베시는 원하는 디렉터리 안으로 이동할 수 있다. 어느 디렉터리에 있든 모든 파일을 상대 경로로 가리킬 수 있고, 상대 경로에서 ..는 부모 디렉터리를 뜻한다. 베시가 folder2 안에 있다면 네 파일을 다음과 같이 가리킨다.

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

상대 경로는 현재 디렉터리에서 목표 파일과의 가장 가까운 공통 조상 디렉터리까지 올라간 다음, 거기서 목표 파일까지 내려가는 경로다. 올라가는 단계마다 ..를 쓰고 내려가는 단계마다 그 디렉터리나 파일의 이름을 쓰며, 각 구성 요소는 /로 잇는다. 경로의 길이는 이렇게 만들어진 문자열의 문자 수다.

베시는 모든 파일까지의 상대 경로 길이 합이 가장 작아지는 디렉터리를 고르려고 한다.

첫째 줄에 파일과 디렉터리의 총 개수 $N$($2 \le N \le 100\,000$)이 주어진다. 입력에서 파일과 디렉터리에는 1 이상 $N$ 이하의 서로 다른 정수 ID가 하나씩 붙고, ID 1은 최상위 디렉터리를 가리킨다.

다음 $N$개 줄에는 ID가 1부터 $N$까지인 파일 또는 디렉터리의 정보가 차례대로 주어진다. 각 줄은 이름으로 시작한다. 이름은 소문자 a부터 z까지와 숫자 0부터 9까지로만 이루어지고, 길이는 16자 이하다. 이름 다음에는 정수 $m$이 온다. $m$이 0이면 이 대상은 파일이다. $m > 0$이면 이 대상은 디렉터리이고, 그 안에 파일이나 디렉터리가 모두 $m$개 들어 있다. $m$ 뒤에는 그 디렉터리에 들어 있는 대상의 ID가 $m$개 주어진다.

모든 파일까지의 상대 경로 길이 합이 가장 작을 때 그 합을 출력한다. 이 값은 32비트 정수에 담기지 않을 수 있다.

첫 번째 예제의 입력은 문제에서 보인 디렉터리 구조와 같다. 가장 좋은 선택은 folder1이고, 그 디렉터리에서 각 파일의 상대 경로는 다음과 같다.

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