P4727 [HNOI2009] 图的同构计数

当学生们遇到某个难题时经常会说“这怎么做，这不是NP问题吗？”、“这个只有搜了，这己经被证明是NP问题了”。但是，你应该淸楚，大多数人此时所说的NP问题其实都是指NPC问题。很多人没有真正掌握NP问题和NPC问题这两个基本概念。其实NP问题并不是那种“只有搜才行”的问题，NPC问题才是。 很久以前就有一个古老的传说：有―个著名的问题，即P是否等于NP的问题，传说中谁要是证明或者证伪了这个命题，他将获得幸福。这里P是指能在多项式时间里求解的问题的集合。而NP是指可在多项式时间里验证的问题的集合。显然P是NP的子集，因为能在多项式时间里求解的问题，必定可在多项式时间里验证。 到目前为止还没有人因这个命题得到幸福。但是，有一个总的趋势，也就是人们普遍认为，$P=NP$不成立，即，多数人相信，至少存在一个不可能有多项式时间复杂度的求解算法的NP问题。人们如此坚信$P \neq NP$是有原因的，因为在研究NP问题的过程中找出了一类非常特殊的NP问题叫做NP-完全问题，也就是所谓的NPC问题。正是因为存在NPC问题，才使人们相信$P \neq NP$。 在提出NPC的概念之后，绝大多数“自然”的难题最后都被证明是NPC问题，只有三个例外，它们分别是： - 线形规划问题； - 图同构问题； - 素数判定问题与大数分解问题。

小雪在了解到以上情况后，自认为直接挑战终极难题还有不少困难，于是决定先从简单的问题做起，具体来说，他对图同构问题产生了浓厚的兴趣。$A$图与$B$图被认为是同构的是指：$A$图的顶点经过一定的重新标号以后，$A$图的顶点集和边集要完全与$B$图一一对应。 小雪现在专注于如何判断两个图是否同构，同时他还想知道两两互不同构的含$N$个点的图有多少种。众所周知含$N$个点的简单图最多有$N*(N-1)/2$条边，这样含$N$个点的图有$2^{N*(N-1)/2}$种可能的情况。显然这些图中有很多图是同构的，小雪想知道的便是：若同构的图算成一种，则有多少种不同的图。他把这个任务丢给了你，在他想出来之前快点解决吧！

无

无

对于 $40 \%$ 的数据，$N \le 20$。 对于 $100 \%$ 的数据，$0 \le N \le 60$。