Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

CSMS0084 - Зүүлт

Циклгүй, холбоост граф өгөгдөв. Өөрөөр хэлбэл аль ч оройноос өөр ямар ч орой руу ирмэгүүдээр дамжин хүрч болдог, цикл агуулаагүй граф өгөгдсөн.
Үнэт эдлэлийн компани ийм графыг ашиглан хүзүүний зүүлт хийх гэж байгаа. Оройнуудыг сувдааг, ирмэгүүдийг алтан гинжээр хийнэ. Хөрш оройнууд өөр өөр төрлийн сувдаар хийгдэх ёстой. Эерэг бүхэл р тоо бүрийн хувд р гэсэн үнэтэй нэг төрлийн сувд байдаг.
Өгөгдсөн загварыг ашиглан хийж болох хүзүүний зүүлтнүүдээс хамгийн бага үнэтэйг ол.

Input

Эхний мөрөнд оройн тоо N (1 ≤ N ≤ 10 000) өгөгдөнө. Оройнуудыг 1-ээс N хүртлэх тоогоор дугаарласан. Дараагийн N-1 ширхэг мөрөнд ирмэг бүрийг тодорхойлно. Эдгээр мөр бүр А, В гэсэн хос бүхэл тоог зайгаар тусгаарлан агуулна (1 ≤ A, B ≤ N, A ≠ B). Энэ хос нь А, В оройг холбосон ирмэгийг илэрхийлнэ.

Output

Загварыг хийхэд хэрэгтэй хамгийн бага нийт үнийг агуулна.

Example

Input:
8
1 2
3 1
1 4
5 6
1 5
5 7
5 8

Output:
11
Тайлбар: 1,2,3 гэсэн үнэтэй гурван төрлийн сувд ашиглаж байна.

Нэмсэн:sw40
Огноо:2009-03-29
Хугацааны хязгаарлалт:1s
Эх кодын хэмжээний хязгаарлалт:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Програмчлалын хэлүүд:Бүгд дараах хэлүүдээс бусад: ADA95 ASM64 BASH BF C++ 4.3.2 C99 CLPS CLOJURE D ERL FSHARP GO ICON ICK JS-RHINO LUA NEM NICE NODEJS OCAML PERL6 PIKE PRLG-swi SCALA SCM guile SCM qobi SED ST TCL VB.NET WHITESPACE

hide comments
2011-08-07 05:08:51 Dunno
huzuunii zuult chin neg cycle aguulmaar l iin. hehe
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.