安全员Orange

题目描述

CEIT由一颗包含 $n$ 个节点的巨大的树组成，其中树的每个节点都代表一个教室。毕老师委派Orange为安全员，Orange每次走之前应该从 $1$ 号节点出发，检查每个教室所在的节点是否留有安全隐患(比如没关窗户或者空调)，并且最后回到 $1$ 号节点，签上安全检查报告才能离开。树的每条边均花费Orange 1个单位的时间。

这严重影响到了Orange每天晚上的游戏时间，但是他又无可奈何。毕老师得知此事后，愿意出资新建一条道路，联通树上的任意两节点，来减少Orange的工作量，你知道Orange应该如何修建这条边，才能让他减少最多的工作量呢？请输出Orange在建立新边之后遍历整个树的时间。

输入格式

第一行包含一个整数 $n$，接下来 $n - 1$ 行，每行包含两个整数 $u, v$，表示这两点之间存在一条边。

数据范围： $1 \le n \le 10^5$

输出格式

一个整数表示答案。

样例 #1

样例输入 #1

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

样例输出 #1

12

提示

在9-5之间建立一条新边，是一种可行的方案。