#P6204. [USACO07CHN] Treasure G

[USACO07CHN] Treasure G

题目描述

卡门和他的朋友们最近挖到了一箱财宝,他们打算将这箱财宝埋在公路网的某个节点上。

整个公路网有 NN 个节点,这些节点之间由 NN 条公路连接。公路都是双向通行的,任何一个节点至少与一条公路相连,且没有节点与超过 44 条公路连接。卡门决定不将财宝埋在有 44 条公路连接的节点上,因为那里交通繁忙,容易被暴露。

卡门将公路网的地图画了出来,并在计划埋藏财宝的地方画了个叉。为了研究最佳埋藏方案,他把所有情况都画了出来,比如下面是一个 N=4N=4 时的所有埋藏情况:

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

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

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

输入格式

第一行一个整数 NN4N1054 \leq N \leq 10^5)。

接下来 NN 行,每行两个整数 u,vu,v1u,vN1 \leq u,v \leq N),描述一条道路。

保证两个节点间最多有一条道路直接相连,且不存在从节点 uu 到节点 uu 的道路。

输出格式

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

4
1 2
2 3
3 1
1 4
3