描述

蚂蚁王国住着N只蚂蚁，每只蚂蚁都有自己的领地，领地之间可以直接到达或者经过其他领地间接到达，可以直接到达的领地之间的道路距离都为1，但所有的领地都有一条唯一的最短路径可以相互到达。

现要在$N$块领地（依次编号为$1$~$N$）中，选出一块领地建立游乐场，使得所有蚂蚁到游乐场的最小路径距离总和是$N$种情况中最小的。

例如：N = 8， 1～8号领地之间的连接关系为： 1和5、2和6、3和6、4和5、5和6、4和7、5和8。如图：

如果将游乐场创建在5号领地，最小距离总和为10。 1号到5号距离为1；2号到5号距离为2；3号到5号距离为2；4号到5号距离为1；6号到5号距离为1；7号到5号距离为2；8号到5号距离为1。

如果将游乐场创建在6号领地，最小距离总和为12。 1号到6号距离为2；2号到6号距离为1；3号到6号距离为1；4号到6号距离为2；5号到6号距离为1；7号到6号距离为3；8号到6号距离为2。

......

可以发现，将游乐场创建在5号领地，最小距离总和10是最小的，故输出10。

输入输出格式

输入

第一行输入一个正整数$N$ ($2≤N≤20$)， 表示领地数量

接下来$N-1$行，每行包含两个正整数 ($1≤正整数≤N$，两个正整数不相同)，表示两块领地相互之间可以直接到达，正整数之间以一个英文逗号隔开（数据保证$N$块领地相互之间可以到达）

输出

输出一个整数，表示$N$种情况中最小距离总和的最小值。

样例

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

10