T259868 「ZHYOI-1」游戏

ZHY 正在玩一种游戏。

游戏规则如下： 给定 $n$，一条直线上的 $n$ 个位置，$n-1$ 条线。$n$ 个位置从左到右编号为 $1$ 到 $n$，$i$ 号位置上初始有 $i$ 号点，第 $i$ 条线连接 $i$ 号点和 $i+1$ 号点，形成了一条链。 现在，系统将这条链随机打乱若干次，每次打乱定义为一次 **操作**：把点提出后，会留出一个空位供其他点左右移动。定义一次 **移动** 为左移或右移一个点，这次移动合法当且仅当移动方向上的下一个位置是空的。最后仍会有一个空位，而系统会把那个提出的点放回去。 经过若干次随机的打乱，第 $i$ 条线的两个端点分别在第 $u_i$ 号和 $v_i$ 号位置。现在，ZHY 需要通过若干次操作把它还原成初始状态。ZHY 希望还原的过程中 **在移动的次数尽可能小的基础上**，进行尽可能少次数的操作。请你告诉他这个最少的 **操作量** 是多少。**保证打乱时的所有移动合法，也就是说数据一定有解。**

第一行一个正整数 $n$。 随后 $n-1$ 行，每行两个正整数 $u_i$ 和 $v_i$，意义如题所述。

输出一行 $1$ 个整数，表示在“移动”次数最少的基础上进行的操作数最小是多少。

#### 样例 $1$ 解释 将 $3$ 号位置上的点提出，将 $2$ 号位置上的点移到 $3$ 号位置，再将提出的点放回。 #### 样例 $2$ 解释 第一次操作：将 $4$ 号位置上的点提出，将 $3$ 号位置上的点移到 $4$ 号位置，将 $2$ 号位置上的点移到 $3$ 号位置，再将提出的点放回。 第二次操作：将 $4$ 号位置上的点提出，将 $3$ 号位置上的点移到 $4$ 号位置，再将提出的点放回。 #### 样例 $3$ 解释 第一次操作：将 $4$ 号位置上的点提出，将 $3$ 号位置上的点移到 $4$ 号位置，再将提出的点放回。 第二次操作：将 $1$ 号位置上的点提出，将 $2$ 号位置上的点移到 $1$ 号位置，再将提出的点放回。 #### 数据范围 对于 $20\%$ 的数据，$n \le 7$。 对于 $60\%$ 的数据，$n \le 2000$。 对于 $100\%$ 的数据，$3 \le n \le 10^5,1 \le u_i,v_i \le n$。**保证打乱时的所有移动合法，也就是说数据一定有解。**