E. Навчнууд дээрх шоргоолжнууд

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Мод гэдэг нь циклгүй холбоост график бөгөөд модны навч гэдэг нь өөрөөсөө гадна яг нэг оройтой холбогдсон оройг хэлнэ.

Танд $n$ ширхэг орой бүхий нэгэн мод өгөгдсөн ба үүний үндэс нь $1$ гэсэн орой дээр байх юм.Түүнчлэн модны навч бүр дээр шоргоолж байгаа бөгөөд нэг секундийн дотор хэсэг шоргоолж нэгэн зэрэг өөрсдийн байгаа оройгоосоо уг оройныхоо эх үүсвэр болсон орой уруугаа шилжин хөдлөх юм.Ямар ч 2 шоргоолж нэгэн зэрэг модны үндэснээс өөр ижил орой дээр байж болохгүй.

Тэгвэл бүх шоргоолж модны үндэс дээр очиход шаардагдах хамгийн бага хугацааг олно уу.Тэмдэглэл: Хөдөлж эхлэхээс өмнө шоргоолжнууд зөвхөн модны навчнууд дээр байгааг анхаарна уу.

Оролт

Эхний мөрөнд модны оройн тоо болох бүхэл тоо $n$ ($2 ≤ n ≤ 5*10^{5}$) өгөгдөнө.

Дараагийн $n - 1$ ширхэг мөрний мөр болгонд $i$-дахь ирмэгийн захын цэгүүд болох 2 бүхэл тоо $x_{i}, y_{i}$ ($1 ≤ x_{i}, y_{i} ≤ n$)-ууд өгөгдөнө.Мөн танд өгөгдсөн мод нь зөв чиглэлгүй мод байх юм.

Гаралт

Бүх шоргоолж модны үндэс дээр очиход шаардагдах хамгийн бага хугацааг илэрхийлэх ганц бүхэл тоо $t$-г хэвлэнэ.

Орчуулсан: Баатархүү

Жишээ тэстүүд

Оролт
12
1 2
1 3
1 4
2 5
2 6
3 7
3 8
3 9
8 10
8 11
8 12
Гаралт
6
Оролт
2
2 1
Гаралт
1
Сэтгэгдлүүдийг ачааллаж байна...