这是一道模板题。

给定一棵以点 $1$ 为根的树，你需要输出这棵树中最多能选出多少个互不同构的子树。

两棵有根树 $T_1$、$T_2$ 同构当且仅当他们的大小相等，且存在一个顶点排列 $\sigma$ 使得在 $T_1$ 中 $i$ 是 $j$ 的祖先当且仅当在 $T_2$ 中 $\sigma (i)$ 是 $\sigma (j)$ 的祖先。

输入格式

第一行一个正整数 $n$，表示树的点数。

接下来 $n-1$ 行给出树边。每行两个正整数 $a,b$，表示树上有一条连接点 $a$ 和点 $b$ 的边。

输出格式

一行一个正整数，表示最多能选出的互不同构的子树个数。

样例一

input

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

output

4

explanation

一种最优的选法是选择 $1$ 号点、$2$ 号点、$3$ 号点、$4$ 号点的子树。

限制与约定

对于所有数据，$1\le n\le {10}^6$。

提示：由于 Hack 机制的存在，不建议使用固定的哈希模数。C++11 中一种安全的随机数生成器为 mt19937_64(chrono::steady_clock::now().time_since_epoch().count())。

时间限制：$5\mathtt{\text{s}}$

空间限制：$512\mathtt{\text{MB}}$