Canmuu 和朋友最近得到大量钚，同意把新宝藏埋在加拿大荒野深处某个路口。埋宝藏总要有藏宝图，于是决定自己画一张。

路网有 $N$ $(4 \le N \le 100,000)$ 个路口（编号 $1..N$），由 $N$ 条路连接。繁忙路口令人困惑，每个路口至少一条路、至多四条路。维护良好，驼鹿总能在任意两个路口之间来回奔跑。Canmuu 决定不埋在四岔路口，因为繁忙交通会降低秘密性。

地图包含所有路和路口。但为了隐藏宝藏位置，只标记埋宝藏的那个路口，当然用大红 'X'。

警觉的驼鹿 Canmuu 试画了地图，看看埋在不同地点会怎样。他发现埋在两个不同地点也可能画出相似地图。好奇的鹿群开始研究能画多少张不同地图。

若能建立如下映射，两图视为相同：

• 两图标 X 的路口对应；

• 其他路口可以建立对应，使得

• 选好路口对应后，连接路口的道路也对应。

例如下图 $N = 4$，宝藏可以埋在四个路口中的任意一个：

        +             +             X           +
       /|            /|            /|          /|
  X---+ |       +---X |       +---+ |     +---+ |
       \|            \|            \|          \|
        +             +             +           X

最后两图相同，因为可建立顶点对应（把图倒过来看），道路便完全对应。因此只有三张不同地图。

给定一组道路，可能有多少张不同地图？

*本题前 10 次提交会获得额外反馈。

输入格式

从标准输入读入。

• 第 1 行：一个整数 $N$。

• 第 2..$N + 1$ 行：两个以空格分隔的整数 $A$、$B$ $(1 \le A \le N; 1 \le B \le N)$，表示路口 $A$、$B$ 之间有路。

输出格式

向标准输出写入。

• 第 1 行：一个整数，不同藏宝图数量。

样例

输入格式 1

4
1 2
2 3
3 1
1 4

输出格式 1

3

说明

下面画出道路和路口。

                   4---1---2
                        \ /
                         3

任意路口都可埋宝藏，但埋在路口 2、3 得到相同地图，因此不同藏宝图总数为 3。

题目作者：Yang Yi，2007