题目描述

卡门和他的朋友们近来得到了一盒财宝，他们打算把它埋在加拿大野外公路网的一个结点上.

公路网包含$\red{N(4<=N<=100000)}$个由$\red{1}$到$\red{N}$编号的结点，和连接它们的$\red{N}$条公路，公路都是双向通行的，任意一个结点至少与一条公路连接，没有结 点与超过$\red{4}$条公路连接，而且，卡门决定财宝不能埋在有$\red{4}$条公路连接的结点上，因为那里交通太繁忙，很容易暴露.

卡门画了公路交通网的地冬，他会在埋藏地上面画了一个大大的叉，为了研究最佳埋藏位置，他给每一种埋藏可能都绘制了地冬，比如，对于一张$\red{N =4}$的地冬，有以下$\red{4}$种埋藏可能。

在仔细研究之后，他发现事实上后两种埋藏方式是一样的，因为后两张地图是相似的，两张地图相似，当且仅当存在某种结点的对应法则，使

宝藏埋藏地相对应

如果两个结点之间有路，则对应结点之间也有路

如果两个结点之间没有路，则对应结点之间也没有路

那么，存在多少种埋藏方式呢?

输入格式

第$\red{1}$行输入$\red{N，}$之后$\red{N}$行每行输入一对整数，描述一条道路．

输出格式

输出宝藏的埋藏方式种数．

样例

输入样例

4
1 2
2 3
3 1
1 4

输出样例

3

提示

输入详细信息：这是一张道路和十字路口的图。

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

输出详细信息：

宝藏可以埋在任何十字路口。然而，在交点$\red{2}$和$\red{3}$生成相互相同的地图。所以不同的藏宝图总数是$\red{3}$。