Hansel 从他母亲那里得到了一串葡萄。他本应与非常喜欢葡萄的 Gretel 分享。Gretel 的行为是可以预见的，所以 Hansel 知道，一旦他折断了这串葡萄中的一根枝条，她就会坚持认为，因为她是女孩，她应该有权选择折断后得到的两部分中的一部分。当然，她会选择浆果数量较多的那一部分。因此，Hansel 希望选择一根枝条，以确保他自己保留的那一部分尽可能多地包含浆果。请帮助他确定他能为自己保证得到的浆果数量。

Hansel 在谈论一串葡萄时使用了一种相当独特的术语。任何这样的一串葡萄都具有树的结构：它由葡萄和枝条组成，每一根枝条直接连接两颗不同的葡萄。任意两颗葡萄之间都由唯一确定的枝条序列连接。其中一颗葡萄被特别指定为根（root）。除了根以外，那些恰好只有一根枝条与其他葡萄相连的葡萄被称为浆果（berries），所有其他葡萄被称为节点（joints）。

输入格式

输入的第一行包含一个整数 $n$ ($2 \le n \le 1\,000\,000$)，表示串中葡萄的数量。葡萄编号从 $1$ 到 $n$，其中根的编号为 $1$。接下来的 $n-1$ 行描述了枝条，每行包含两个整数 $a$ 和 $b$ ($a \neq b, 1 \le a, b \le n$)，表示编号为 $a$ 和 $b$ 的葡萄之间直接由一根枝条相连。

输出格式

输出的第一行也是唯一一行应包含 Hansel 通过适当地选择枝条所能保证为自己获得的最大浆果数量。

样例

输入格式 1

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

输出格式 1

2

说明

上图展示了样例中的葡萄串。每颗浆果用圆圈表示，所有其他葡萄（即节点）用方块表示。连接圆圈和方块的线段代表枝条。Hansel 可以通过折断粗线段所代表的任意一根枝条，来保证获得编号为 5 和 6 的浆果。剩下的编号为 7、8、9 的浆果则归 Gretel 所有。