你所在的城市刚刚完成了新的交通网络 PlusRail 的建设。该网络共有 $n$ 个车站，且任意两个车站之间有且仅有一条路径，这是因为网络中只有 $n - 1$ 条直接连接的线路。换句话说，该网络构成了一棵树。

你受雇为每个车站制作标识牌，标识牌上会画出网络结构，并用一个大箭头指向位于中心位置的亮红色车站。

图 G.1：样例 1 的说明，展示了两种设计如何被重复使用四次，并通过在不同位置标注车站名称来实现。

由于网络图纸相当粗糙，实际上你可以将同一个设计用于多个车站，只需为车站名称填写不同的排列组合即可。

如果你想为整个网络制作标识牌，你最少需要多少种独特的设计？

输入格式

• 第一行包含车站数量 $n$ ($1 \le n \le 3 \times 10^5$)。
• 接下来的 $n - 1$ 行，每行包含两个不同的顶点编号 $a$ 和 $b$ ($1 \le a, b \le n$)，表示这两个车站之间有一条直接线路。

输出格式

输出最少需要的地图设计数量，使得对于任意车站，至少有一种地图设计可以通过重新标注，让该车站处于中心位置。

样例

样例输入 1

4
1 2
2 3
3 4

样例输出 1

2

样例输入 2

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

样例输出 2

10

样例输入 3

7
7 1
7 2
3 2
7 4
5 4
6 5

样例输出 3

7