题目描述

Byteotia 的铁路网并不发达。铁路网由 $n$ 座城市以及连接这些城市的双向铁路组成。

任意两座城市之间都恰好存在一条“合理路线”，这里的合理路线是指一条不会重复经过任何城市的路线。对于每一对城市，都有一列火车沿着它们之间的合理路线运行。

目前，Byteotia 的所有铁路都还没有电气化，列车全部由笨重、难闻且耗油量巨大的内燃机车牵引。具体来说，内燃机车每经过一段连接两座相邻城市的铁路，就会消耗 $1$ 百升燃油。

Byteotia 的决策者决定改善铁路运输。在修建新铁路之前，他们打算先对现有铁路进行电气化：修建接触网支柱、架设电线，并让轻便、清洁且不消耗燃油的电力动车组投入运行。

有两家公司参加了铁路现代化改造的招标：Szerokie Tory（ST） 和 Podkłady i Tłuczeń（PiT）。最终决定，两家公司都将获得一项工程。

每家公司将选择某两座城市之间的一条合理路线，并把这条路线上的所有铁路电气化。

分配给两家公司的两条路线不能相交，也就是说，它们不能经过同一座城市。由于两家公司的员工关系非常紧张，因此必须避免他们在任何城市相遇。

改造完成后，仍然要保持任意两座城市之间的列车服务。列车在行驶过程中可以根据铁路是否已经电气化，在内燃机车和电力列车之间进行切换。

请选择两条互不相交的合理路线进行电气化，使得所有列车总共消耗的燃油量最少。

计算总燃油消耗时，假设每一对城市之间的合理路线上恰好有一列火车，并且只沿一个方向行驶一次。

输入格式

第一行包含一个整数 $n$，表示 Byteotia 的城市数量。

接下来 $n-1$ 行，每行包含两个整数 $a_i,b_i$，表示城市 $a_i$ 和城市 $b_i$ 之间有一条直接相连的双向铁路。

保证给出的铁路网满足：任意两座城市之间恰好存在一条不重复经过城市的路径。

输出格式

输出一个整数，表示完成最优电气化方案后，所有列车总共消耗的燃油量，单位为百升。

样例输入

6
1 3
2 3
3 4
4 5
4 6

样例输出

9

样例说明

ST 可以将路线 $1\to3\to2$ 电气化，PiT 可以将路线 $6\to4\to5$ 电气化。

这样唯一没有被电气化的铁路是 $3-4$。共有 $9$ 条合理路线会经过这条铁路，因此所有列车总共会消耗 $9$ 百升燃油。

数据范围

$2\le n\le 500000$。

对于每条铁路，$1\le a_i,b_i\le n$ 且 $a_i\ne b_i$。