Беси хранит свои файлы на компьютере в виде коллекции директорий.
bessie/
folder1/
file1
folder2/
file2
folder3/
file3
file4
Самая верхняя директория называется bessie
Беси может заходить в любую директорию, какую захочет. Из данной директории
любой файл может быть доступен по "относительному пути". В относительном пути
символ ".." означает родительскую директорию. Например, если Беси находится в
директории folder2, то она может обращаться к своим четырём файлам следующим
образом:
../file1
file2
../../folder3/file3
../../file4
Беси хочет выбрать такую директорию, из которой сумма длин относительных
путей ко всем файлам минимальна.
ФОРМАТ ВВОДА (файл dirtraverse.in):
Первая строка содержит целое число N (
\(2 \leq N \leq 100,000\)), определяющее
общее количество файлов и директорий. В целях упрощения ввода каждому объекту
(файлу или директории) назначено уникальное целое число (ID) от 1 до
\(N\), где
1 означает самую верхнюю директорию.
Далее следуют \(N\) строк. Каждая строка начинается с имени файла или директории.
Имя состоит только из маленьких английских букв a-z и цифр 0-9 и имеет длину не более
16 символов. Следом за именем идёт целое число \(m\). Если \(m\) равно 0, значит это файл.
Если \(m > 0\), значит это директория, которая содержит \(m\) файлов или директорий.
Следующие \(m\) целых чисел содержат идентификаторы объектов в этой директории.
ФОРМАТ ВЫВОДА (файл dirtraverse.out):
Выведите минимально возможную длину всех относительных путей к файлам.
Заметим, что это число может таким большим, что не поместится в 32-битное целое.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|