Kataloqun gəzintisi#10412

Kataloqun gəzintisi

1 saniyə

128 meqabayt

Asan

İnək Bessi kompüterlərdə təəccüblü dərəcədə yaxşı başa düşür. Anbardakı kompüterində o, bütün qiymətli fayllarını kataloq sistemində saxlayır, məsələn:

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

Yalnız bir ən üst səviyyəli kataloq var, o, bessie adlanır.

Bessi istənilən kataloqa keçə bilər. Cari kataloqdan istənilən fayla nisbi yol vasitəsilə müraciət etmək mümkündür, burada .. simvolu valideyn kataloqu bildirir. Məsələn, əgər Bessi folder2 kataloqundadırsa, o, dörd fayla aşağıdakı kimi müraciət edə bilər:

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

Bessi elə bir kataloq seçmək istəyir ki, bütün fayllara olan nisbi yolların ümumi uzunluğu minimal olsun.

Giriş

Birinci sətirdə ümumi fayl və kataloqların sayını bildirən $n (2 \leq n \leq 1 0^{5})$ n~(2 \le n \le 10^5) tam ədədi verilir. Hər obyektə (fayl və ya kataloqa) $1$ -dən $n$ -ə qədər unikal tam ədəd nömrəsi verilir, bu zaman $1$ nömrəsi ən üst səviyyəli kataloqa uyğun gəlir.

Sonrakı $n$ sətirdən hər biri bir obyekti təsvir edir. Sətir fayl və ya kataloqun adı ilə başlayır. Ad yalnız kiçik latın hərflərindən (' $a$ ' – ' $z$ ') və rəqəmlərdən (' $0$ ' – ' $9$ ') ibarətdir, onun uzunluğu $16$ simvoldan çox deyil. Addan sonra $m$ tam ədədi gəlir. Əgər $m = 0$ m = 0 olarsa, obyekt fayldır. Əgər $m > 0$ m > 0 olarsa, obyekt birbaşa $m$ fayl və ya kataloq saxlayan kataloqdur; bu halda sonra bu kataloqda yerləşən obyektlərin $m$ nömrəsi göstərilir.

Çıxış

Bütün fayllara olan nisbi yolların mümkün olan ən kiçik ümumi uzunluğunu çap edin. Diqqət edin ki, bu qiymət $32$ -bitlik tam ədəd tipinə sığmaya bilər.

Nümunələr

Ən optimal variant folder1 kataloqunda olmaqdır. Bu kataloqdan nisbi yollar aşağıdakı kimidir:

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

Nümunə 1