D. Поло пенгвин ба мод

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

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

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

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

Бяцхан Поло пенгвинд мод байна. Мод гэдэг нь $n$ оройтой, $n-1$ ирмэгтэй, чиглэлгүй, холбоост, циклгүй граф юм. Бид модны оройнуудыг $1$-ээс $n$ хүртэл дугаарласан гэж үзнэ.

Өнөөдөр Поло ерөнхий оройгүй замуудын хосуудын тоог хэрхэн олох вэ гэж бодож байна. Томъёолбол тэр:

  • $1 ≤ a < b ≤ n$;
  • $1 ≤ c < d ≤ n$;
  • $a$-аас $b$ орой руу мөн $c$-ээс $d$ орой руу хүрэх хамгийн богино зам дээр хоёулан дээр нь орших орой байхгүй байх $a,b,c,d$ дөрвөн бүхэл тооны бүлгийн тоог олох ёстой юм.

Хоёр оройн хоорондох хамгийн богино зам гэдэг нь эдгээрийн хоорондох ирмэгийн хамгийн бага тоо юм.

Энэ бодлогыг бодоход Поло пенгвинд туслана уу.

Оролт

Эхний мөрөнд бүхэл $n$ $(1 ≤ n ≤ 80000)$ тоо агуулагдана. Энэ нь модны зангилаануудын тоо юм. Дараагийн $n - 1$ мөр бүрт хос бүхэл $u_{i}$ ба $v_{i}$ $(1 ≤ u_{i}, v_{i} ≤ n; u_{i} ≠ v_{i})$ тоонууд агуулагдана. Энэ нь модны $i$-р ирмэг юм.

Оролтод өгөгдөх граф нь гарцаагүй мод байх болно.

Гаралт

Бодлогын хариулт болох нэг бүхэл тоог нэг мөрөнд хэвлэнэ.

С++ хэлний оролт гаралтын хэлбэрт 64-битийн тоог дүрслэхдээ \%lld-г бүү хэрэглээрэй. Харин cin, cout эсвэл \%I64d хэлбэрийг ашиглавал тохиромжтой.

Орчуулсан: Даариймаа

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

Оролт
4
1 2
2 3
3 4
Гаралт
2
Сэтгэгдлүүдийг ачааллаж байна...