题目描述

卡门和他的朋友们最近挖到了一箱财宝，他们打算将这箱财宝埋在公路网的某个节点上。 整个公路网有 $n$ 个节点，这些节点之间由 $n$ 条公路连接。公路都是双向通行的，任何一个节点至少与一条公路相连，且没有节点与超过 $4$ 条公路连接。卡门决定不将财宝埋在有 $4$ 条公路连接的节点上，因为那里交通繁忙，容易被暴露。 卡门将公路网的地图画了出来，并在计划埋藏财宝的地方画了个叉。为了研究最佳埋藏方案，他把所有情况都画了出来，比如下面是一个 $n=4$ 时的所有埋藏情况：

他仔细研究后，发现后两种方案是本质相同的。两种地图是本质相同的，当且仅当：

• 宝藏埋藏地点相对应；
• 如果两个节点间有路，则对应节点间也有路；
• 如果两个节点间没有路，则对应节点间也没有路。

现在你需要求出究竟有多少种本质不同的埋藏方案。

输入格式

第一行一个整数 $n$。 接下来 $n$ 行，每行两个整数 $u,v$，描述一条道路。 保证两个节点间最多有一条道路直接相连，且不存在从节点 $u$ 到节点 $u$ 的道路。

输出格式

输出本质不同的埋藏方案数。

4
1 2
2 3
3 1
1 4

3

数据规模与约定

对于 $100\%$ 的数据，$4 \leq n \leq 10^5$，$1 \leq u,v \leq n$。

题目来源

Gold