Cô bò Bessie am hiểu máy tính một cách đáng ngạc nhiên. Trên chiếc máy tính trong chuồng, cô lưu tất cả các tệp quý giá của mình trong một hệ thống thư mục; chẳng hạn:

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

Chỉ có một thư mục “cấp cao nhất”, tên là bessie.

Bessie có thể di chuyển để ở bên trong bất kỳ thư mục nào cô muốn. Từ một thư mục cho trước, có thể tham chiếu đến bất kỳ tệp nào bằng một “đường dẫn tương đối”. Trong một đường dẫn tương đối, ký hiệu .. chỉ thư mục cha. Nếu Bessie đang ở trong folder2, cô có thể tham chiếu đến bốn tệp như sau:

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

Bessie muốn chọn một thư mục sao cho tổng độ dài các đường dẫn tương đối từ thư mục đó đến tất cả các tệp là nhỏ nhất.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên \(N\) (\(2 \leq N \leq 100{,}000\)), là tổng số tệp và thư mục. Trong dữ liệu vào, mỗi đối tượng (tệp hoặc thư mục) được gán một ID nguyên duy nhất từ \(1\) đến \(N\), trong đó ID \(1\) chỉ thư mục cấp cao nhất.

Tiếp theo là \(N\) dòng. Mỗi dòng bắt đầu bằng tên của một tệp hoặc thư mục. Tên chỉ gồm các chữ cái thường a-z và các chữ số 0-9, đồng thời dài không quá \(16\) ký tự. Sau tên là một số nguyên \(m\). Nếu \(m\) bằng \(0\) thì đối tượng này là một tệp. Nếu \(m > 0\) thì đối tượng này là một thư mục và chứa tổng cộng \(m\) tệp hoặc thư mục bên trong nó. Sau \(m\) là \(m\) số nguyên cho biết ID của các đối tượng nằm trong thư mục này.

Dữ liệu ra

In ra tổng độ dài nhỏ nhất có thể của các đường dẫn tương đối đến các tệp. Lưu ý rằng giá trị này có thể quá lớn để lưu trong một số nguyên \(32\) bit.

Ví dụ

8
bessie 3 2 6 8
folder1 2 3 4
file1 0
folder2 1 5
file2 0
folder3 1 7
file3 0
file4 0

42

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

Nguồn

USACO 2018 February Contest, Gold — Directory Traversal

Tác giả bài toán: Mark Gordon.