#204. 严神的商店 III

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: syzoj

题目描述

严神又准备开一家商店, 这次他突然发现, 街道变成了一个奇怪的结构。

sampleGraph.png

这次的居民都住在 n 个居民点上,每个居民点都有一个居民。 居民点之间用 n - 1 条双向道路连接。 每个居民的不悦指数定义为该居民到商店所需经过的最少道路数。 多个居民的不悦指数等于这些居民的不悦指数之和。

严神想知道, 如果他在这里开一家商店, 居民们的不悦指数最少是多少。

输入格式

输入共 n 行。

1 行, 一个整数 m , 代表居民点的数量。

接下来 n - 1 行, 每行 2 个整数 x , y . 代表居民点 x y 有一条双向道路联通。

我们保证每两个居民点均可以通过道路直接或间接联通。两个居民点之间至多有的一条道路联通。

输出格式

输出仅一个整数, 最小的不悦指数。

样例

输入样例 1

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

输出样例 1

7

数据范围与提示

本题采用捆绑测试。

子任务 分数 n m
1 5 \leq 100 \leq 10^3
2 11 \leq 500 \leq 5 \cdot 10^3
3 12 \leq 10^3
4 19 \leq 2 \cdot 10^3 \leq 5 \cdot 10^4
5 23 \leq 2 \cdot 10^5
6 30 \leq 5 \cdot 10^3 \leq 3 \cdot 10^5