题目描述

老师有一棵有 n 个结点的树，结点依次以 1,2,…,n 编号。

老师想将这棵树作为奖品分给两位同学。具体而言，老师会选择一条边并从树上删去它，从而将这棵树分为两个连通块。两位同学分别可以得到其中一个连通块。

如果有同学拿到的连通块结点数明显小于另一位同学，那么这位同学会不太高兴。为了避免这种情况出现，老师想知道两个连通块结点数之差的绝对值最小是多少。

输入格式

第一行，一个正整数 n，表示结点数量。接下来 n−1 行，每行两个正整数 u_i,v_i，表示树上有一条连接结点 u_i 和结点 v_i 的边。

输出格式

输出一行，一个整数，表示删除一条边后两个连通块结点数之差的绝对值最小值。

样例

样例输入 1

4
1 2
2 3
3 4

样例输出 1

0

样例输入 2

6
1 2
1 3
1 4
1 5
5 6

样例输出 2

2

数据范围

对于 40% 的测试点，保证 2≤n≤500；对于所有测试点，保证 2≤n≤2×10^4。