Migrated from Lutece 3074 生活在树上

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

又是一年炎热的夏天，$\text{Bob Wang}$ 已经无法忍受来自地上升腾的热气，因此他做了一个决定——生活在树上！

$\text{Bob Wang}$ 先是找到了一颗自己喜爱的树，可是很不幸的是有很多人也喜欢这棵树，并且先于 $\text{Bob Wang}$，已经在树上搭好树屋了。

$\text{Bob Wang}$ 只能在树上再修一间树屋。具体地，在他到来之前，这棵树上就已经有 $n$ 间树屋了，编号从 $1$ 到 $n$，每间树屋可以看作树上的一个结点，这些树屋通过无向边相连便构成了这棵树。$\text{Bob Wang}$ 可以在任何一间树屋旁边再修一间树屋，编号为 $n+1$，显然他的树屋必然是叶子结点。然而为了防止这棵树倒塌，每间树屋相邻的树屋的数量不能超过 $4$ 个，这个性质在 $\text{Bob Wang}$ 来之前就已经满足了，在他修好树屋后也必须满足。

$\text{Bob Wang}$ 修树屋的速度很快，然而爱思考的他提出了一个问题，在他修建完他的树屋后，这棵树的形态最多可能有多少种？ $\text{}$ 树的同构性的定义如下：

若一个长度为 $n$ 的序列 $p_1,p_2,\ldots,p_n$ 中出现了 $1\sim n$ 中所有的数（每个数恰好出现一次），则称该序列为一个长度为 $n$ 的排列。

两棵 $n$ 个点的树 A 和树 B 的形态不同，当且仅当不存在任何一个排列 $p_1,p_2,\ldots,p_n$，使得对于任意一个数对 $(u,v)$，若在 A 树中存在边 $(u,v)$，则在 B 树中存在边 $(p_u,p_v)$。

Input

第一行一个整数 $n$，表示在 $\text{Bob Wang}$ 来之前树上的树屋数。

接下来 $n-1$ 行，每行两个整数 $u$ 和 $v$，表示编号为 $u$ 的树屋与编号为 $v$ 的树屋是相邻的。

Output

一行一个整数，表示在 $\text{Bob Wang}$ 修建完他的树屋后，这棵树的形态最多可能有多少种。

Samples

4
1 2
2 3
2 4

2

5
1 2
1 3
1 4
1 5

1

5
2 5
5 3
4 3
4 1

3

Constraints

$1\leq n\leq 10^5$

Note

数据保证所有树屋一定会构成一棵树，并且最开始与每间树屋相邻的树屋数量不超过 $4$ 个。

Resources

2023 UESTC ICPC Training for String