Background

Special for beginners, ^_^

Description

小C是一位城市规划师，负责设计一个城市的交通网络。这个城市有 n 个地点，每个地点都用一个节点表示，并且这些节点通过道路连接成一棵树状结构的交通网络。

现在，小C需要选择两条道路进行改造，以改善交通流量和连通性。小C希望通过断掉这两条道路，将交通网络分成三个连通块，使得每个连通块的规模尽可能均衡，即节点数的差异最小。

小C希望找到一个最佳的改造方案，使得最大连通块和最小连通块之间的节点数差异最小化。这样做可以提高城市的交通效率和可访问性，使得居民能够更方便地出行和互连。

也就是说，选择两条边断掉后形成三个连通块，这三个连通块内的点数分别为a,b,c，那么请你最小化max{a,b,c}−min{a,b,c} 的大小，并求这个最小值。

Format

Input

第一行一个整数 n 代表树的点数。

接下来 n−1 行，每行两个整数 x,y 代表树的一条边。

Output

一行一个整数代表答案。

Samples

4
1 2
2 3
3 4

1

【样例1说明】

能构造的最优解三个连通块的点数都为1,1,2，所以输出2−1=1。

6
1 2
1 3
3 4
3 5
5 6

0

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

2

Limitation

对于25%的测试点：3<n<=200;

对于50%的测试点：3<n<=2000;

对于100%的测试点：3<n<=2*10​^5​;