You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

烤乐滋即将在 A 市开设一家店铺，已知 A 市的结构呈树状，并且每两个节点距离为 $1$ ，她想知道店铺开在哪个节点能使从所有节点到这家店铺的距离之和最小，请你帮她找出这个最小距离之和。

输入格式

第一行一个正整数 $n$，表示节点数量。

第二行到第 $n$ 行，每行两个正整数 $x,y$，中间用空格隔开，表示第 $x$ 个节点和第 $y$ 个节点中间有一条长度为 $1$ 的路。

输出格式

一行一个整数，表示最小距离之和。

输入样例

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

输出样例

14

数据范围

本题同类型测试点采用捆绑测试。

对于 $50\%$ 的数据，$1 \le n \le 10$。

对于 $100\%$ 的数据，满足 $1 \le x,y \le n \le 10^5$ 。