题目描述

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

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

输入格式

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

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

输出格式

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

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

4

样例分析

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

数据范围与提示

对于 $100\%$ 的数据，$1 \le n \le 10^6$。