在图论绘图中，有根（连通）树 $T = (V, E)$ 的线性排列是指一种平面绘图，其中树的 $n$ 个顶点被放置在水平线（即 $x$ 轴）上，而 $(n - 1)$ 条边被绘制为连接其端点的上方半圆弧，如图 1 所示。这种线性排列 $\pi$ 将每个顶点映射为一个从 1 到 $n$ 的不同整数，代表其在 $x$ 轴上的坐标。

图 1.（左）以顶点 1 为根的九顶点有根树 $T$。（中）$T$ 的一种整洁排列。（右）$T$ 的一种不整洁排列，因为红色边 $(3, 7)$ 覆盖了根节点。

在线性排列 $\pi$ 中，两个顶点 $u$ 和 $v$ 之间的距离 $d(u, v)$ 定义为它们 $x$ 坐标之差，即 $d(u, v) = |\pi(u) - \pi(v)|$。形式上，对于有根树 $T = (V, E)$，线性排列 $\pi$ 的代价定义为 $\sum_{(u, v) \in E} d(u, v)$。

有根树 $T$ 的整洁排列 $\pi$ 是一种满足以下两个条件的特殊线性排列：

1. $\pi$ 中不存在除公共端点外的边交叉。
2. 没有边覆盖 $T$ 的根节点 $r$，即不存在边 $(u, v)$ 使得 $\pi(u) < \pi(r) < \pi(v)$。

例如，图 1 中间的是左侧树 $T$ 的一种整洁排列，而右侧的不是整洁排列，因为边 $(3, 7)$ 覆盖了根节点 1。中间整洁排列的代价为 11，其中有三条距离为 2 的边和五条距离为 1 的边。该代价是 $T$ 所有整洁排列中的最小值。

给定一棵以顶点 1 为根的有根树，编写一个程序，输出该树整洁排列的最小可能代价。

输入格式

程序从标准输入读取数据。输入的第一行包含一个整数 $n$ ($2 \le n \le 5,000$)，表示有根树的顶点数。顶点编号从 1 到 $n$，根节点为 1。接下来的 $(n - 1)$ 行，每行包含两个正整数 $u$ 和 $v$，表示树的一条（无向）边 $(u, v)$ 的两个端点，其中 $u$ 和 $v$ 是 1 到 $n$ 之间不同的整数。

输出格式

程序向标准输出写入数据。输出仅一行，包含以顶点 1 为根的树的整洁排列的最小代价。

样例

输入 1

4
1 2
3 2
2 4

输出 1

4

输入 2

9
2 4
2 5
7 3
9 7
1 2
3 1
7 8
6 2

输出 2

11